imported>David Eppstein: Diameter (graph theory)

2024-12-30T02:39:17Z

New page

{{Short description|Graph where any two nodes of equal distance are isomorphic}}
{{No footnotes|date=September 2021}}[[Image:BiggsSmith.svg|thumb|right|The [[Biggs-Smith graph]], the largest [[Cubic graph|3-regular]] distance-transitive graph.]]
{{Graph families defined by their automorphisms}}

In the [[mathematics|mathematical]] field of [[graph theory]], a '''distance-transitive graph''' is a [[Graph (discrete mathematics)|graph]] such that, given any two [[Vertex (graph theory)|vertices]] {{mvar|v}} and {{mvar|w}} at any [[Distance (graph theory)|distance]] {{mvar|i}}, and any other two vertices {{mvar|x}} and {{mvar|y}} at the same distance, there is an [[Graph automorphism|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 group]]s are the automorphism groups of distance-transitive graphs, especially of those whose [[Diameter (graph theory)|diameter]] is 2.

== Examples ==
Some first examples of families of distance-transitive graphs include:
* The [[Johnson graph]]s.
* The [[Grassmann graph]]s.
* The [[Hamming graph|Hamming Graphs]] (including [[Hypercube graph]]s).
* The [[folded cube graph]]s.
* The square [[rook's graph]]s.
* The [[Livingstone graph]].

== Classification of cubic distance-transitive graphs ==
After introducing them in 1971, [[Norman L. Biggs|Biggs]] and Smith showed that there are only 12 finite connected [[cubic graph|trivalent]] distance-transitive graphs. These are:
{| class="wikitable" border="1"
|-
! Graph name
! Vertex count
! [[Diameter (graph theory)|Diameter]]
! [[Girth (graph theory)|Girth]]
! [[Intersection array]]
|-
| [[Tetrahedral graph]] or [[complete graph]] K<sub>4</sub> || 4 || 1 || 3 || {3;1}
|-
| [[complete bipartite graph]] K<sub>3,3</sub> || 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}
|}

== Relation to distance-regular graphs ==
Every distance-transitive graph is [[distance-regular graph|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]]

Distance-transitive graph - Revision history

imported>David Eppstein: Diameter (graph theory)