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ív	${\displaystyle {\boldsymbol {\rightarrow }}}$	távolságreguláris	${\displaystyle {\boldsymbol {\leftarrow }}}$	erősen reguláris
${\displaystyle {\boldsymbol {\downarrow }}}$
szimmetrikus	${\displaystyle {\boldsymbol {\leftarrow }}}$	t-tranzitív, t ≥ 2		ferdeszimmetrikus
${\displaystyle {\boldsymbol {\downarrow }}}$
(ha összefüggő) csúcs- és éltranzitív	${\displaystyle {\boldsymbol {\rightarrow }}}$	éltranzitív és reguláris	${\displaystyle {\boldsymbol {\rightarrow }}}$	éltranzitív
${\displaystyle {\boldsymbol {\downarrow }}}$		${\displaystyle {\boldsymbol {\downarrow }}}$		${\displaystyle {\boldsymbol {\downarrow }}}$
csúcstranzitív	${\displaystyle {\boldsymbol {\rightarrow }}}$	reguláris	${\displaystyle {\boldsymbol {\rightarrow }}}$	(ha páros) bireguláris
${\displaystyle {\boldsymbol {\uparrow }}}$
Cayley-gráf	${\displaystyle {\boldsymbol {\leftarrow }}}$	zérószimmetrikus		aszimmetrikus

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

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ó 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

• 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 és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

1. Brouwer et al. 1989, pp. 221-225

Korai cikkek

• .
• .
• .
• .
• .

Felmérések

• , chapter 20.
• .
• , chapter 7.
• .
• , section 4.5.
• .

További információk

• Weisstein, Eric W.: Distance-Transitive Graph (angol nyelven). Wolfram MathWorld

• Matematikaportál • összefoglaló, színes tartalomajánló lap