Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Distance-transitive graph
Summary
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.
Some first examples of families of distance-transitive graphs include:
The Johnson graphs.
The Grassmann graphs.
The Hamming Graphs.
The folded cube graphs.
The square rook's graphs.
The hypercube graphs.
The Livingstone graph.
After introducing them in 1971, Biggs and Smith showed that there are only 12 finite trivalent distance-transitive graphs. These are:
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.