Login
Login

distance-transitive graph

{{Short description|Graph where any two nodes of equal distance are isomorphic}}

{{No footnotes|date=September 2021}}Image:BiggsSmith.svg, the largest 3-regular distance-transitive graph.]]

{{Graph families defined by their automorphisms}}

In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices {{mvar|v}} and {{mvar|w}} at any distance {{mvar|i}}, and any other two vertices {{mvar|x}} and {{mvar|y}} at the same distance, there is an automorphism of the graph that carries {{mvar|v}} to {{mvar|x}} and {{mvar|w}} to {{mvar|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.

Examples

Some first examples of families of distance-transitive graphs include:

Classification 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:

class="wikitable" border="1"
Graph name

! Vertex count

! Diameter

! Girth

! Intersection array

Tetrahedral graph or complete graph K4413{3;1}
complete bipartite graph K3,3624{3,2;1,3}
Petersen graph1025{3,2;1,1}
Cubical graph834{3,2,1;1,2,3}
Heawood graph1436{3,2,2;1,1,3}
Pappus graph1846{3,2,2,1;1,1,2,3}
Coxeter graph2847{3,2,2,1;1,1,1,2}
Tutte–Coxeter graph3048{3,2,2,2;1,1,1,3}
Dodecahedral graph2055{3,2,1,1,1;1,1,1,2,3}
Desargues graph2056{3,2,2,1,1;1,1,2,2,3}
Biggs-Smith graph10279{3,2,2,2,1,1,1;1,1,1,1,1,1,3}
Foster graph90810{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}

Relation 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.

References

;Early works

  • {{citation

| last1 = Adel'son-Vel'skii | first1 = G. M. | authorlink1 = Georgy Adelson-Velsky

| last2 = Veĭsfeĭler | first2 = B. Ju. |authorlink2 = Boris Weisfeiler

| last3 = Leman | first3 = A. A.

| last4 = Faradžev | first4 = I. A.

| title = An example of a graph which has no transitive group of automorphisms

| journal = Doklady Akademii Nauk SSSR | volume = 185 | pages = 975–976 | year = 1969

| mr = 0244107}}.

  • {{citation

| last = Biggs | first = Norman

| contribution = Intersection matrices for linear graphs

| year = 1971

| title = Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969)

| pages = 15–23 | publisher = Academic Press | location = London

| mr = 0285421}}.

  • {{citation

| last = Biggs | first = Norman

| title = Finite Groups of Automorphisms

| series = London Mathematical Society Lecture Note Series

| volume = 6 | publisher = Cambridge University Press | location = London & New York | year = 1971

| mr = 0327563}}.

  • {{citation

| last1 = Biggs | first1 = N. L.

| last2 = Smith | first2 = D. H.

| title = On trivalent graphs

| journal = Bulletin of the London Mathematical Society

| volume = 3 | year = 1971 | pages = 155–158

| mr = 0286693

| doi = 10.1112/blms/3.2.155

| issue = 2}}.

  • {{citation

| last = Smith | first = D. H.

| title = Primitive and imprimitive graphs

| journal = The Quarterly Journal of Mathematics |series=Second Series

| volume = 22 | year = 1971 | pages = 551–557

| mr = 0327584

| doi = 10.1093/qmath/22.4.551

| issue = 4}}.

;Surveys

  • {{citation

| last = Biggs | first = N. L.

| chapter = Distance-Transitive Graphs

| title = Algebraic Graph Theory | edition = 2nd

| publisher = Cambridge University Press | pages = 155–163 | year = 1993}}, chapter 20.

  • {{citation

| last = Van Bon | first = John

| title = Finite primitive distance-transitive graphs

| journal = European Journal of Combinatorics

| volume = 28 | year = 2007 | issue = 2 | pages = 517–532

| mr = 2287450

| doi = 10.1016/j.ejc.2005.04.014| doi-access = free}}.

  • {{citation

| last1 = Brouwer | first1 = A. E. | author1-link = Andries Brouwer | last2 = Cohen | first2 = A. M. | last3 = Neumaier | first3 = A.

| chapter = Distance-Transitive Graphs

| title = Distance-Regular Graphs | location = New York | publisher = Springer-Verlag | pages = 214–234 | year = 1989}}, chapter 7.

  • {{citation

| last = Cohen | first = A. M. Cohen

| contribution = Distance-transitive graphs

| editor1-first = L. W. | editor1-last = Beineke

| editor2-first = R. J. | editor2-last = Wilson

| title = Topics in Algebraic Graph Theory

| series = Encyclopedia of Mathematics and its Applications

| volume = 102 | publisher = Cambridge University Press | year = 2004 | pages = 222–249}}.

  • {{citation

| last1 = Godsil | first1 = C. | author1-link = Chris Godsil

| last2 = Royle | first2 = G. | author2-link = Gordon Royle

| chapter = Distance-Transitive Graphs

| title = Algebraic Graph Theory | location = New York | publisher = Springer-Verlag | pages = 66–69 | year = 2001}}, section 4.5.

  • {{citation

| last = Ivanov | first = A. A.

| contribution = Distance-transitive graphs and their classification

| editor1-first = I. A. | editor1-last = Faradžev

| editor2-last = Ivanov | editor2-first = A. A.

| editor3-last = Klin | editor3-first = M.

|display-editors = 3 | editor4-last = Woldar | editor4-first = A. J.

| title = The Algebraic Theory of Combinatorial Objects

| series = Math. Appl. (Soviet Series) | volume = 84 | publisher = Kluwer

| location = Dordrecht | year = 1992 | pages = 283–378

| mr = 1321634}}.

External links

  • {{mathworld|title=Distance-Transitive Graph|urlname=Distance-TransitiveGraph}}

Category:Algebraic graph theory

Category:Graph families

Category:Regular graphs