Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Distance-transitive graph
open-in-new
<h2 id="examples">Examples</h2> <p>Some first examples of families of distance-transitive graphs include: </p> <ul><li>The <a href="/facts/Johnson_graph/LtUdcvPt">Johnson graphs</a>.</li> <li>The <a href="/facts/Grassmann_graph/YdsN1lLa">Grassmann graphs</a>.</li> <li>The <a href="/facts/Hamming_graph/fqdyerpu">Hamming Graphs</a> (including <a href="/facts/Hypercube_graph/pwfGEl9J">Hypercube graphs</a>).</li> <li>The <a href="/facts/Folded_cube_graph/wpQyUsh8">folded cube graphs</a>.</li> <li>The square <a href="/facts/Rook%27s_graph/EqVx5BPA">rook's graphs</a>.</li> <li>The <a href="/facts/Livingstone_graph/b2XTQGKw">Livingstone graph</a>.</li></ul> <h2 id="classification-of-cubic-distance-transitive-graphs">Classification of cubic distance-transitive graphs</h2> <p>After introducing them in 1971, <a href="/facts/Norman_L._Biggs/PXXEVgPP">Biggs</a> and Smith showed that there are only 12 finite connected <a href="/facts/Cubic_graph/6M32WUIJ">trivalent</a> distance-transitive graphs. These are: </p> <table><tbody><tr><th>Graph name</th><th>Vertex count</th><th><a href="/facts/Diameter_(graph_theory)/EmQFKvqa">Diameter</a></th><th><a href="/facts/Girth_(graph_theory)/rPwRGgxj">Girth</a></th><th><a href="/facts/Intersection_array/pGAuLWYL">Intersection array</a></th></tr><tr><td><a href="/facts/Tetrahedral_graph/7mkSrl6j">Tetrahedral graph</a> or <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> K4</td><td>4</td><td>1</td><td>3</td><td>{3;1}</td></tr><tr><td><a href="/facts/Complete_bipartite_graph/C1RYIdpX">complete bipartite graph</a> K3,3</td><td>6</td><td>2</td><td>4</td><td>{3,2;1,3}</td></tr><tr><td><a href="/facts/Petersen_graph/lLRxXpQs">Petersen graph</a></td><td>10</td><td>2</td><td>5</td><td>{3,2;1,1}</td></tr><tr><td><a href="/facts/Cubical_graph/65lUaAqN">Cubical graph</a></td><td>8</td><td>3</td><td>4</td><td>{3,2,1;1,2,3}</td></tr><tr><td><a href="/facts/Heawood_graph/ymqQSkIK">Heawood graph</a></td><td>14</td><td>3</td><td>6</td><td>{3,2,2;1,1,3}</td></tr><tr><td><a href="/facts/Pappus_graph/w40dHpA6">Pappus graph</a></td><td>18</td><td>4</td><td>6</td><td>{3,2,2,1;1,1,2,3}</td></tr><tr><td><a href="/facts/Coxeter_graph/A4DpQ90A">Coxeter graph</a></td><td>28</td><td>4</td><td>7</td><td>{3,2,2,1;1,1,1,2}</td></tr><tr><td><a href="/facts/Tutte%E2%80%93Coxeter_graph/SH13hLkX">Tutte–Coxeter graph</a></td><td>30</td><td>4</td><td>8</td><td>{3,2,2,2;1,1,1,3}</td></tr><tr><td><a href="/facts/Dodecahedral_graph/xClYqhcp">Dodecahedral graph</a></td><td>20</td><td>5</td><td>5</td><td>{3,2,1,1,1;1,1,1,2,3}</td></tr><tr><td><a href="/facts/Desargues_graph/M6sXWfFK">Desargues graph</a></td><td>20</td><td>5</td><td>6</td><td>{3,2,2,1,1;1,1,2,2,3}</td></tr><tr><td><a href="/facts/Biggs-Smith_graph/UDEzxCPI">Biggs-Smith graph</a></td><td>102</td><td>7</td><td>9</td><td>{3,2,2,2,1,1,1;1,1,1,1,1,1,3}</td></tr><tr><td><a href="/facts/Foster_graph/f5Clb9vA">Foster graph</a></td><td>90</td><td>8</td><td>10</td><td>{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}</td></tr></tbody></table> <h2 id="relation-to-distance-regular-graphs">Relation to distance-regular graphs</h2> <p>Every distance-transitive graph is <a href="/facts/Distance-regular_graph/pGAuLWYL">distance-regular</a>, but the converse is not necessarily true. </p><p>In 1969, before publication of the Biggs–Smith definition, a Russian group led by <a href="/facts/Georgy_Adelson-Velsky/1CpLURAR">Georgy Adelson-Velsky</a> 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 <a href="/facts/Shrikhande_graph/NVH1YV71">Shrikhande graph</a>, with 16 vertices and degree 6. The only graph of this type with degree three is the 126-vertex <a href="/facts/Tutte_12-cage/NrkGdHjh">Tutte 12-cage</a>. 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. </p> Early works <ul><li><a href="/facts/Georgy_Adelson-Velsky/1CpLURAR">Adel'son-Vel'skii, G. M.</a>; <a href="/facts/Boris_Weisfeiler/d24zlWdl">Veĭsfeĭler, B. Ju.</a>; Leman, A. A.; Faradžev, I. A. (1969), "An example of a graph which has no transitive group of automorphisms", <i><a href="/facts/Doklady_Akademii_Nauk_SSSR/dqes3C9S">Doklady Akademii Nauk SSSR</a></i>, 185: 975–976, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0244107">0244107</a>.</li> <li>Biggs, Norman (1971), "Intersection matrices for linear graphs", <i>Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969)</i>, London: Academic Press, pp. 15–23, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0285421">0285421</a>.</li> <li>Biggs, Norman (1971), <i>Finite Groups of Automorphisms</i>, London Mathematical Society Lecture Note Series, vol. 6, London & New York: Cambridge University Press, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0327563">0327563</a>.</li> <li>Biggs, N. L.; Smith, D. H. (1971), "On trivalent graphs", <i>Bulletin of the London Mathematical Society</i>, 3 (2): 155–158, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1112%2Fblms%2F3.2.155">10.1112/blms/3.2.155</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0286693">0286693</a>.</li> <li>Smith, D. H. (1971), "Primitive and imprimitive graphs", <i>The Quarterly Journal of Mathematics</i>, Second Series, 22 (4): 551–557, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1093%2Fqmath%2F22.4.551">10.1093/qmath/22.4.551</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0327584">0327584</a>.</li></ul> Surveys <ul><li>Biggs, N. L. (1993), "Distance-Transitive Graphs", <i>Algebraic Graph Theory</i> (2nd ed.), Cambridge University Press, pp. 155–163, chapter 20.</li> <li>Van Bon, John (2007), "Finite primitive distance-transitive graphs", <i>European Journal of Combinatorics</i>, 28 (2): 517–532, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2Fj.ejc.2005.04.014">10.1016/j.ejc.2005.04.014</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2287450">2287450</a>.</li> <li><a href="/facts/Andries_Brouwer/zdSqHqHR">Brouwer, A. E.</a>; Cohen, A. M.; Neumaier, A. (1989), "Distance-Transitive Graphs", <i>Distance-Regular Graphs</i>, New York: Springer-Verlag, pp. 214–234, chapter 7.</li> <li>Cohen, A. M. Cohen (2004), "Distance-transitive graphs", in Beineke, L. W.; Wilson, R. J. (eds.), <i>Topics in Algebraic Graph Theory</i>, Encyclopedia of Mathematics and its Applications, vol. 102, Cambridge University Press, pp. 222–249.</li> <li><a href="/facts/Chris_Godsil/ygA2pwGf">Godsil, C.</a>; <a href="/facts/Gordon_Royle/D5QQ6qkt">Royle, G.</a> (2001), "Distance-Transitive Graphs", <i>Algebraic Graph Theory</i>, New York: Springer-Verlag, pp. 66–69, section 4.5.</li> <li>Ivanov, A. A. (1992), "Distance-transitive graphs and their classification", in Faradžev, I. A.; Ivanov, A. A.; Klin, M.; et al. (eds.), <i>The Algebraic Theory of Combinatorial Objects</i>, Math. Appl. (Soviet Series), vol. 84, Dordrecht: Kluwer, pp. 283–378, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1321634">1321634</a>.</li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/Distance-TransitiveGraph.html">"Distance-Transitive Graph"</a>. <i><a href="/facts/MathWorld/yc1jodbq">MathWorld</a></i>.</li></ul>