Examples
Combining the symmetry condition with the restriction that graphs be cubic (i.e. all vertices have degree 3) yields quite a strong condition, and such graphs are rare enough to be listed. The Foster census and its extensions provide such lists. The Foster census was begun in the 1930s by Ronald M. Foster while he was employed by Bell Labs, and in 1988 (when Foster was 92) the then current Foster census (listing all cubic symmetric graphs up to 512 vertices) was published in book form. The first thirteen items in the list are cubic symmetric graphs with up to 30 vertices (ten of these are also distance transitive; the exceptions are as indicated):
| Vertices | Diameter | Girth | Graph | Notes |
|---|---|---|---|---|
| 4 | 1 | 3 | The complete graph K4 | distance transitive, 2-transitive |
| 6 | 2 | 4 | The complete bipartite graph K3,3 | distance transitive, 3-transitive |
| 8 | 3 | 4 | The vertices and edges of the cube | distance transitive, 2-transitive |
| 10 | 2 | 5 | The Petersen graph | distance transitive, 3-transitive |
| 14 | 3 | 6 | The Heawood graph | distance transitive, 4-transitive |
| 16 | 4 | 6 | The Möbius–Kantor graph | 2-transitive |
| 18 | 4 | 6 | The Pappus graph | distance transitive, 3-transitive |
| 20 | 5 | 5 | The vertices and edges of the dodecahedron | distance transitive, 2-transitive |
| 20 | 5 | 6 | The Desargues graph | distance transitive, 3-transitive |
| 24 | 4 | 6 | The Nauru graph (the generalized Petersen graph G(12,5)) | 2-transitive |
| 26 | 5 | 6 | The F26A graph | 1-transitive |
| 28 | 4 | 7 | The Coxeter graph | distance transitive, 3-transitive |
| 30 | 4 | 8 | The Tutte–Coxeter graph | distance transitive, 5-transitive |
Other well known cubic symmetric graphs are the Dyck graph, the Foster graph and the Biggs–Smith graph. The ten distance-transitive graphs listed above, together with the Foster graph and the Biggs–Smith graph, are the only cubic distance-transitive graphs.
Non-cubic symmetric graphs include cycle graphs (of degree 2), complete graphs (of degree 4 or more when there are 5 or more vertices), hypercube graphs (of degree 4 or more when there are 16 or more vertices), and the graphs formed by the vertices and edges of the octahedron, icosahedron, cuboctahedron, and icosidodecahedron. The Rado graph forms an example of a symmetric graph with infinitely many vertices and infinite degree.
Read more about this topic: Symmetric Graph
Famous quotes containing the word examples:
“It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
—G.C. (Georg Christoph)
“There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring ‘em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.”
—Bernard Mandeville (1670–1733)
“No rules exist, and examples are simply life-savers answering the appeals of rules making vain attempts to exist.”
—André Breton (1896–1966)