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.

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ák Néhány példa távolságtranzitív gráfcsaládokra: A Johnson-gráfok. A Grassmann-gráfok. A Hamming-gráfok (benne a hiperkockagráfok, teljes gráfok, négyzetes bástyagráfok) hajtott kockagráfok (folded cube graphs).

A távolságtranzitív gráfok osztályozása

Az összes, 13-nál nem nagyobb fokszámú véges távolságtranzitív gráf ismert,Brouwer et al. 1989, pp. 221-225 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ó kapcsolata 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ás

Jegyzetek

Korai cikkek . . . . .

Felmérések , chapter 20. . , chapter 7. . , section 4.5. .

További információk

Kategória:Algebrai gráfelmélet Kategória:Gráfcsaládok Kategória:Reguláris gráfok