Distance-transitive graph: Difference between revisions
m →References: wikilink Andries Brouwer |
m →Examples: Combine Hamming graphs and Hypercube graphs |
||
(45 intermediate revisions by 34 users not shown) | |||
Line 1: | Line 1: | ||
{{Short description|Graph where any two nodes of equal distance are isomorphic}} |
|||
[[Image:BiggsSmith.svg|thumb|right|The |
{{No footnotes|date=September 2021}}[[Image:BiggsSmith.svg|thumb|right|The [[Biggs-Smith graph]], the largest [[Cubic graph|3-regular]] distance-transitive graph.]] |
||
⚫ | In [[mathematics]], a '''distance-transitive graph''' is a [[ |
||
{{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 [[Vertex-transitive graph|vertex transitive]] and [[Symmetric graph|symmetric]] as well as [[Distance-regular graph|distance regular]]. |
|||
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 is 2. |
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 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 == |
|||
⚫ | |||
{| class="wikitable" border="1" |
{| class="wikitable" border="1" |
||
|- |
|- |
||
! Graph name |
! Graph name |
||
! Vertex count |
! Vertex count |
||
! [[Diameter]] |
! [[Distance (graph theory)|Diameter]] |
||
! [[Girth (graph theory)|Girth]] |
! [[Girth (graph theory)|Girth]] |
||
! [[Intersection array]] |
! [[Intersection array]] |
||
|- |
|- |
||
| [[complete graph]] K<sub>4</sub> || 4 || 1 || 3 || {3;1} |
| [[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} |
| [[complete bipartite graph]] K<sub>3,3</sub> || 6 || 2 || 4 || {3,2;1,3} |
||
Line 21: | Line 32: | ||
| [[Petersen graph]] || 10 || 2 || 5 || {3,2;1,1} |
| [[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} |
| [[Heawood graph]] || 14 || 3 || 6 || {3,2,2;1,1,3} |
||
Line 27: | Line 38: | ||
| [[Pappus graph]] || 18 || 4 || 6 || {3,2,2,1;1,1,2,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} |
| [[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} |
| [[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} |
| [[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} |
| [[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== |
==References== |
||
Line 48: | Line 61: | ||
*{{citation |
*{{citation |
||
| last1 = Adel'son-Vel'skii | first1 = G. M. | authorlink1 = Georgy Adelson-Velsky |
| last1 = Adel'son-Vel'skii | first1 = G. M. | authorlink1 = Georgy Adelson-Velsky |
||
| last2 = Veĭsfeĭler | first2 = B. Ju. |
| last2 = Veĭsfeĭler | first2 = B. Ju. |authorlink2 = Boris Weisfeiler |
||
| last3 = Leman | first3 = A. A. |
| last3 = Leman | first3 = A. A. |
||
| last4 = Faradžev | first4 = I. A. |
| last4 = Faradžev | first4 = I. A. |
||
| title = An example of a graph which has no transitive group of automorphisms |
| title = An example of a graph which has no transitive group of automorphisms |
||
| journal = |
| journal = [[Doklady Akademii Nauk SSSR]] | volume = 185 | pages = 975–976 | year = 1969 |
||
| |
| mr = 0244107}}. |
||
*{{citation |
*{{citation |
||
| last = Biggs | first = Norman |
| last = Biggs | first = Norman |
||
Line 61: | Line 73: | ||
| title = Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) |
| title = Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) |
||
| pages = 15–23 | publisher = Academic Press | location = London |
| pages = 15–23 | publisher = Academic Press | location = London |
||
| |
| mr = 0285421}}. |
||
*{{citation |
*{{citation |
||
| last = Biggs | first = Norman |
| last = Biggs | first = Norman |
||
Line 68: | Line 79: | ||
| series = London Mathematical Society Lecture Note Series |
| series = London Mathematical Society Lecture Note Series |
||
| volume = 6 | publisher = Cambridge University Press | location = London & New York | year = 1971 |
| volume = 6 | publisher = Cambridge University Press | location = London & New York | year = 1971 |
||
| |
| mr = 0327563}}. |
||
*{{citation |
*{{citation |
||
| last1 = Biggs | first1 = N. L. |
| last1 = Biggs | first1 = N. L. |
||
Line 76: | Line 86: | ||
| journal = Bulletin of the London Mathematical Society |
| journal = Bulletin of the London Mathematical Society |
||
| volume = 3 | year = 1971 | pages = 155–158 |
| volume = 3 | year = 1971 | pages = 155–158 |
||
| |
| mr = 0286693 |
||
| doi = 10.1112/blms/3.2.155 |
| doi = 10.1112/blms/3.2.155 |
||
| issue = 2}}. |
|||
*{{citation |
*{{citation |
||
| last = Smith | first = D. H. |
| last = Smith | first = D. H. |
||
| title = Primitive and imprimitive graphs |
| title = Primitive and imprimitive graphs |
||
| journal = The Quarterly Journal of Mathematics |
| journal = The Quarterly Journal of Mathematics |series=Second Series |
||
| volume = 22 | year = 1971 | pages = 551–557 |
| volume = 22 | year = 1971 | pages = 551–557 |
||
| |
| mr = 0327584 |
||
| doi = 10.1093/qmath/22.4.551 |
| doi = 10.1093/qmath/22.4.551 |
||
| issue = 4}}. |
|||
;Surveys |
;Surveys |
||
Line 93: | Line 104: | ||
| title = Algebraic Graph Theory | edition = 2nd |
| title = Algebraic Graph Theory | edition = 2nd |
||
| publisher = Cambridge University Press | pages = 155–163 | year = 1993}}, chapter 20. |
| publisher = Cambridge University Press | pages = 155–163 | year = 1993}}, chapter 20. |
||
*{{citation |
*{{citation |
||
| last = Van Bon | first = John |
| last = Van Bon | first = John |
||
Line 99: | Line 109: | ||
| journal = European Journal of Combinatorics |
| journal = European Journal of Combinatorics |
||
| volume = 28 | year = 2007 | issue = 2 | pages = 517–532 |
| volume = 28 | year = 2007 | issue = 2 | pages = 517–532 |
||
| |
| mr = 2287450 |
||
| doi = 10.1016/j.ejc.2005.04.014}}. |
| doi = 10.1016/j.ejc.2005.04.014| doi-access = free}}. |
||
*{{citation |
*{{citation |
||
| last1 = Brouwer | first1 = A. E. | author1-link = Andries Brouwer | last2 = Cohen | first2 = A. M. | last3 = Neumaier | first3 = A. |
| last1 = Brouwer | first1 = A. E. | author1-link = Andries Brouwer | last2 = Cohen | first2 = A. M. | last3 = Neumaier | first3 = A. |
||
| chapter = Distance-Transitive Graphs |
| chapter = Distance-Transitive Graphs |
||
| title = Distance-Regular Graphs | location = New York | publisher = Springer-Verlag | pages = 214–234 | year = 1989}}, chapter 7. |
| title = Distance-Regular Graphs | location = New York | publisher = Springer-Verlag | pages = 214–234 | year = 1989}}, chapter 7. |
||
*{{citation |
*{{citation |
||
| last = Cohen | first = A. M. Cohen |
| last = Cohen | first = A. M. Cohen |
||
Line 115: | Line 123: | ||
| series = Encyclopedia of Mathematics and its Applications |
| series = Encyclopedia of Mathematics and its Applications |
||
| volume = 102 | publisher = Cambridge University Press | year = 2004 | pages = 222–249}}. |
| volume = 102 | publisher = Cambridge University Press | year = 2004 | pages = 222–249}}. |
||
*{{citation |
*{{citation |
||
| last1 = Godsil | first1 = C. |
| last1 = Godsil | first1 = C. | author1-link = Chris Godsil |
||
| last2 = Royle | first2 = G. |
| last2 = Royle | first2 = G. | author2-link = Gordon Royle |
||
| chapter = Distance-Transitive Graphs |
| chapter = Distance-Transitive Graphs |
||
| title = Algebraic Graph Theory | location = New York | publisher = Springer-Verlag | pages = 66–69 | year = 2001}}, section 4.5. |
| title = Algebraic Graph Theory | location = New York | publisher = Springer-Verlag | pages = 66–69 | year = 2001}}, section 4.5. |
||
*{{citation |
*{{citation |
||
| last = Ivanov | first = A. A. |
| last = Ivanov | first = A. A. |
||
Line 128: | Line 134: | ||
| editor2-last = Ivanov | editor2-first = A. A. |
| editor2-last = Ivanov | editor2-first = A. A. |
||
| editor3-last = Klin | editor3-first = M. |
| editor3-last = Klin | editor3-first = M. |
||
| editor4-last = Woldar | editor4-first = A. J. |
|display-editors = 3 | editor4-last = Woldar | editor4-first = A. J. |
||
| title = The Algebraic Theory of Combinatorial Objects |
| title = The Algebraic Theory of Combinatorial Objects |
||
| series = Math. Appl. (Soviet Series) | volume = 84 | publisher = Kluwer |
| series = Math. Appl. (Soviet Series) | volume = 84 | publisher = Kluwer |
||
| location = Dordrecht | year = 1992 | pages = 283–378 |
| location = Dordrecht | year = 1992 | pages = 283–378 |
||
| |
| mr = 1321634}}. |
||
==External links== |
==External links== |
||
Line 139: | Line 145: | ||
[[Category:Algebraic graph theory]] |
[[Category:Algebraic graph theory]] |
||
[[Category:Graph families]] |
[[Category:Graph families]] |
||
[[Category:Regular graphs]] |
Latest revision as of 11:39, 8 March 2024
This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (September 2021) |
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.
Examples[edit]
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.
Classification of cubic distance-transitive graphs[edit]
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} |
Relation to distance-regular graphs[edit]
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[edit]
- Early works
- Adel'son-Vel'skii, G. M.; Veĭsfeĭler, B. Ju.; Leman, A. A.; Faradžev, I. A. (1969), "An example of a graph which has no transitive group of automorphisms", Doklady Akademii Nauk SSSR, 185: 975–976, MR 0244107.
- Biggs, Norman (1971), "Intersection matrices for linear graphs", Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), London: Academic Press, pp. 15–23, MR 0285421.
- Biggs, Norman (1971), Finite Groups of Automorphisms, London Mathematical Society Lecture Note Series, vol. 6, London & New York: Cambridge University Press, MR 0327563.
- Biggs, N. L.; Smith, D. H. (1971), "On trivalent graphs", Bulletin of the London Mathematical Society, 3 (2): 155–158, doi:10.1112/blms/3.2.155, MR 0286693.
- Smith, D. H. (1971), "Primitive and imprimitive graphs", The Quarterly Journal of Mathematics, Second Series, 22 (4): 551–557, doi:10.1093/qmath/22.4.551, MR 0327584.
- Surveys
- Biggs, N. L. (1993), "Distance-Transitive Graphs", Algebraic Graph Theory (2nd ed.), Cambridge University Press, pp. 155–163, chapter 20.
- Van Bon, John (2007), "Finite primitive distance-transitive graphs", European Journal of Combinatorics, 28 (2): 517–532, doi:10.1016/j.ejc.2005.04.014, MR 2287450.
- Brouwer, A. E.; Cohen, A. M.; Neumaier, A. (1989), "Distance-Transitive Graphs", Distance-Regular Graphs, New York: Springer-Verlag, pp. 214–234, chapter 7.
- Cohen, A. M. Cohen (2004), "Distance-transitive graphs", in Beineke, L. W.; Wilson, R. J. (eds.), Topics in Algebraic Graph Theory, Encyclopedia of Mathematics and its Applications, vol. 102, Cambridge University Press, pp. 222–249.
- Godsil, C.; Royle, G. (2001), "Distance-Transitive Graphs", Algebraic Graph Theory, New York: Springer-Verlag, pp. 66–69, section 4.5.
- Ivanov, A. A. (1992), "Distance-transitive graphs and their classification", in Faradžev, I. A.; Ivanov, A. A.; Klin, M.; et al. (eds.), The Algebraic Theory of Combinatorial Objects, Math. Appl. (Soviet Series), vol. 84, Dordrecht: Kluwer, pp. 283–378, MR 1321634.