Distance-transitive graph
Graph where any two nodes of equal distance are isomorphic
In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices v and w at any distance i, and any other two vertices x and y at the same distance, there is an automorphism of the graph that carries v to x and w to y. Distance-transitive graphs were first defined in 1971 by Norman L. Biggs and D. H. Smith.
A distance-transitive graph is interesting partly because it has a large automorphism group. Some interesting finite groups are the automorphism groups of distance-transitive graphs, especially of those whose diameter is 2.
01Examples
Some first examples of families of distance-transitive graphs include:
- The Johnson graphs.
- The Grassmann graphs.
- The Hamming Graphs (including Hypercube graphs).
- The folded cube graphs.
- The square rook's graphs.
- The Livingstone graph.
02Classification of cubic distance-transitive graphs
After introducing them in 1971, Biggs and Smith showed that there are only 12 finite connected trivalent distance-transitive graphs. These are:
| Graph name | Vertex count | Diameter | Girth | Intersection array |
|---|---|---|---|---|
| Tetrahedral graph or complete graph K4 | 4 | 1 | 3 | {3;1} |
| complete bipartite graph K3,3 | 6 | 2 | 4 | {3,2;1,3} |
| Petersen graph | 10 | 2 | 5 | {3,2;1,1} |
| Cubical graph | 8 | 3 | 4 | {3,2,1;1,2,3} |
| Heawood graph | 14 | 3 | 6 | {3,2,2;1,1,3} |
| Pappus graph | 18 | 4 | 6 | {3,2,2,1;1,1,2,3} |
| Coxeter graph | 28 | 4 | 7 | {3,2,2,1;1,1,1,2} |
| Tutte-Coxeter graph | 30 | 4 | 8 | {3,2,2,2;1,1,1,3} |
| Dodecahedral graph | 20 | 5 | 5 | {3,2,1,1,1;1,1,1,2,3} |
| Desargues graph | 20 | 5 | 6 | {3,2,2,1,1;1,1,2,2,3} |
| Biggs-Smith graph | 102 | 7 | 9 | {3,2,2,2,1,1,1;1,1,1,1,1,1,3} |
| Foster graph | 90 | 8 | 10 | {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3} |
03Relation to distance-regular graphs
Every distance-transitive graph is distance-regular, but the converse is not necessarily true.
In 1969, before publication of the Biggs-Smith definition, a Russian group led by Georgy Adelson-Velsky showed that there exist graphs that are distance-regular but not distance-transitive. The smallest distance-regular graph that is not distance-transitive is the Shrikhande graph, with 16 vertices and degree 6. The only graph of this type with degree three is the 126-vertex Tutte 12-cage. Complete lists of distance-transitive graphs are known for some degrees larger than three, but the classification of distance-transitive graphs with arbitrarily large vertex degree remains open.
Sources and credits
This article is adapted from the Wikipedia article “Distance-transitive graph”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.
Images, from Wikimedia Commons:
- BiggsSmith.svg by Stolee at English Wikipedia, Public domain
Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.