Vzdálenost-tranzitivní graf - Distance-transitive graph

The Biggs-Smithův graf, největší 3-pravidelný přechodový graf vzdálenosti.
Skupiny grafů definované jejich automorfismy
vzdálenost-tranzitivní→vzdálenost-pravidelná←velmi pravidelné
↓
symetrický (oblouk-tranzitivní)←t-tranzitivní, t ≥ 2šikmo symetrický
↓
(je-li připojen)
vrchol a hrana-tranzitivní		→hrana-tranzitivní a pravidelná→hrana tranzitivní
↓↓↓
vrchol-tranzitivní→pravidelný→(pokud je bipartitní)
biregular
↑
Cayleyův graf←nulově symetrickýasymetrický

V matematický pole teorie grafů, a vzdálenost-tranzitivní graf je graf takové, že vzhledem k jakýmkoli dvěma vrcholům proti a w na kterékoli vzdálenost ia další dva vrcholy X a y ve stejné vzdálenosti existuje automorfismus grafu, který nese proti na X a w nay. Vzdálenostně přechodné grafy byly poprvé definovány v roce 1971 uživatelem Norman L. Biggs a D. H. Smith.

Distanční graf je zajímavý částečně proto, že má velký automorfická skupina. Některé zajímavé konečné skupiny jsou automorfické skupiny dálkově přechodných grafů, zejména těch, jejichž průměr je 2.

Příklady

Některé první příklady rodin grafů přechodových vzdáleností zahrnují:

Klasifikace kubických vzdálenostně přechodných grafů

Po jejich zavedení v roce 1971 Biggs a Smith ukázal, že existuje pouze 12 konečných trojmocný vzdálenosti-tranzitivní grafy. Tyto jsou:

Název grafuPočet vrcholůPrůměrObvodKřižovatkové pole
kompletní graf K.4413{3;1}
kompletní bipartitní graf K.3,3624{3,2;1,3}
Petersenův graf1025{3,2;1,1}
Graf krychle834{3,2,1;1,2,3}
Heawoodův graf1436{3,2,2;1,1,3}
Pappusův graf1846{3,2,2,1;1,1,2,3}
Coxeterův graf2847{3,2,2,1;1,1,1,2}
Tutte – Coxeterův graf3048{3,2,2,2;1,1,1,3}
Graf dvanáctistěn2055{3,2,1,1,1;1,1,1,2,3}
Desargues graf2056{3,2,2,1,1;1,1,2,2,3}
Biggs-Smithův graf10279{3,2,2,2,1,1,1;1,1,1,1,1,1,3}
Pěstounský graf90810{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}

Vztah k pravidelným grafům vzdálenosti

Každý přechodový graf vzdálenosti je vzdálenost-pravidelná, ale konverzace nemusí být nutně pravdivá.

V roce 1969, před zveřejněním definice Biggs – Smith, vedla ruská skupina Georgy Adelson-Velsky ukázal, že existují grafy, které jsou pravidelné, ale nikoli přechodné. Jediným grafem tohoto typu se stupněm tři je vrchol 126 Tutte 12-klec. Nejmenší pravidelný graf vzdálenosti, který není přechodný, je Shrikhandův graf. Kompletní seznamy přechodových grafů jsou známé pro některé stupně větší než tři, ale klasifikace dálkově přechodných grafů s libovolně velkým stupněm vrcholu zůstává otevřená.

Reference

Raná díla
  • Adel'son-Vel'skii, G. M.; Veĭsfeĭler, B. Ju.; Leman, A. A .; Faradžev, I. A. (1969), „Příklad grafu, který nemá přechodnou skupinu automorfismů“, Doklady Akademii Nauk SSSR, 185: 975–976, PAN  0244107.
  • Biggs, Norman (1971), „Intersection matrices for linear graphs“, Kombinatorická matematika a její aplikace (Proc. Conf., Oxford, 1969)„London: Academic Press, s. 15–23, PAN  0285421.
  • Biggs, Norman (1971), Konečné skupiny automorfismů, Série přednášek London Mathematical Society, 6, Londýn a New York: Cambridge University Press, PAN  0327563.
  • Biggs, N.L .; Smith, D. H. (1971), „On trivalent graphs“, Bulletin of London Mathematical Society, 3 (2): 155–158, doi:10.1112 / blms / 3.2.155, PAN  0286693.
  • Smith, D. H. (1971), „Primitivní a imprimitivní grafy“, Quarterly Journal of Mathematics. Oxford. Druhá série, 22 (4): 551–557, doi:10.1093 / qmath / 22.4.551, PAN  0327584.
Průzkumy
  • Biggs, N. L. (1993), „Distance-Transitive Graphs“, Algebraická teorie grafů (2. vyd.), Cambridge University Press, str. 155–163, kapitola 20.
  • Van Bon, John (2007), „Konečné primitivní grafy přechodné vzdálenosti“, European Journal of Combinatorics, 28 (2): 517–532, doi:10.1016 / j.ejc.2005.04.014, PAN  2287450.
  • Brouwer, A. E.; Cohen, A. M .; Neumaier, A. (1989), "Distance-Transitive Graphs", Vzdálené pravidelné grafy, New York: Springer-Verlag, s. 214–234, kapitola 7.
  • Cohen, A. M. Cohen (2004), „Distance-transitive graphs“, v Beineke, L. W .; Wilson, R. J. (eds.), Témata v algebraické teorii grafůEncyklopedie matematiky a její aplikace, 102, Cambridge University Press, s. 222–249.
  • Godsil, C.; Royle, G. (2001), „Distance-Transitive Graphs“, Algebraická teorie grafů, New York: Springer-Verlag, s. 66–69, oddíl 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.), Algebraická teorie kombinatorických objektů, Math. Appl. (Sovětská série), 84, Dordrecht: Kluwer, s. 283–378, PAN  1321634.

externí odkazy