Távolságtranzitív gráf

A matematika, azon belül a gráfelmélet területén egy távolságtranzitív gráf (distance-transitive graph) olyan reguláris gráf, melynek bármely két, i távolságra lévő v és w csúcsát és ugyanolyan távolságra lévő tetszőleges x és y csúcsút tekintve van olyan automorfizmus, ami v-t x-be, illetve w-t y-ba viszi. A távolságtranzitív gráfokat elsőként Norman L. Biggs és D. H. Smith definiálták, 1971-ben.

Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitívtávolságreguláriserősen reguláris
szimmetrikust-tranzitív, t ≥ 2ferdeszimmetrikus
(ha összefüggő)
csúcs- és éltranzitív
éltranzitív és reguláriséltranzitív
csúcstranzitívreguláris(ha páros)
bireguláris
Cayley-gráfzérószimmetrikusaszimmetrikus

A távolságtranzitív gráfok főleg azért érdekesek, mert nagy automorfizmus-csoporttal rendelkeznek. Egyes érdekes véges csoportok távolságtranzitív gráfok automorfizmus-csoportjaként állnak elő, főleg azok, melyek 2 átmérőjűek.

PéldákSzerkesztés

Néhány példa távolságtranzitív gráfcsaládokra:

A távolságtranzitív gráfok osztályozásaSzerkesztés

 
A legnagyobb 3-reguláris távolságtranzitív gráf, a Biggs–Smith-gráf.

Az összes, 13-nál nem nagyobb fokszámú véges távolságtranzitív gráf ismert,[1] de a nagyobb fokszámú gráfok osztályozása még nyitott kérdés.

Ezek közül 1971-es bemutatásuk után elsőként Biggs és Smith mutatták meg, hogy csak 12 véges 3-reguláris távolságtranzitív gráf létezik. Ezek a következők:

Gráf neve Csúcsok száma Átmérő Girth Metszési tömb
K4 teljes gráf 4 1 3 {3;1}
K3,3 teljes páros gráf 6 2 4 {3,2;1,3}
Petersen-gráf 10 2 5 {3,2;1,1}
kockagráf 8 3 4 {3,2,1;1,2,3}
Heawood-gráf 14 3 6 {3,2,2;1,1,3}
Papposz-gráf 18 4 6 {3,2,2,1;1,1,2,3}
Coxeter-gráf 28 4 7 {3,2,2,1;1,1,1,2}
Tutte–Coxeter-gráf 30 4 8 {3,2,2,2;1,1,1,3}
dodekaédergráf 20 5 5 {3,2,1,1,1;1,1,1,2,3}
Desargues-gráf 20 5 6 {3,2,2,1,1;1,1,2,2,3}
Biggs–Smith-gráf 102 7 9 {3,2,2,2,1,1,1;1,1,1,1,1,1,3}
Foster-gráf 90 8 10 {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}

Távolságreguláris gráfokkal való kapcsolataSzerkesztés

Minden távolságtranzitív gráf távolságreguláris (azok általánosításai), de fordítva nem feltétlenül van így.

1969-ben egy Georgij Adelson-Velszkij vezetésével működő orosz munkacsoport kimutatta, hogy léteznek olyan távolságreguláris gráfok, melyek nem távolságtranzitívak. A legkisebb ilyen tulajdonságú gráf a Shrikhande-gráf, a 3-reguláris gráfok közül pedig az egyetlen a 126 csúcsból álló Tutte 12-cage.

FordításSzerkesztés

  • Ez a szócikk részben vagy egészben a Distance-transitive graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

JegyzetekSzerkesztés

  1. Brouwer et al. 1989, pp. 221-225
Korai cikkek
  • Adel'son-Vel'skii, G. M.; Veĭsfeĭler, B. Ju. & Leman, A. A. et al. (1969), "An example of a graph which has no transitive group of automorphisms", Doklady Akademii Nauk SSSR 185: 975–976.
  • Biggs, Norman (1971), "Intersection matrices for linear graphs", Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), London: Academic Press, pp. 15–23.
  • Biggs, Norman (1971), Finite Groups of Automorphisms, vol. 6, London Mathematical Society Lecture Note Series, London & New York: Cambridge University Press.
  • 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.
  • Smith, D. H. (1971), "Primitive and imprimitive graphs", The Quarterly Journal of Mathematics. Oxford. Second Series 22 (4): 551–557, DOI 10.1093/qmath/22.4.551.
Felmérések
  • 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.
  • 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., Topics in Algebraic Graph Theory, vol. 102, Encyclopedia of Mathematics and its Applications, 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., The Algebraic Theory of Combinatorial Objects, vol. 84, Math. Appl. (Soviet Series), Dordrecht: Kluwer, pp. 283–378.

További információkSzerkesztés