Távolság-tranzitív gráf

A távolság - tranzitív gráf olyan gráf , amelyben bármely rendezett csúcspárt bármely másik rendezett csúcspárrá fordítja le, amelynek csúcsai közötti távolság az egyik gráf automorfizmusa megegyezik .

A közeli fogalom egy távolság-reguláris gráf , de természetük más. Ha egy távolság-tranzitív gráf a gráf szimmetriájából az automorfizmus feltételén keresztül van definiálva, akkor a távolság-reguláris gráf a kombinatorikus szabályszerűségének feltételéből. Minden távolság-tranzitív gráf távolságszabályos, de ennek fordítva nem igaz. Ezt 1969-ben bebizonyították, még a „távolság-tranzitív gráf” kifejezés megalkotása előtt.

A 13-nál kisebb fokos távolságszabályos grafikonok teljesen osztályozottak.

A távolság-tranzitív gráf definíciói

A távolság-tranzitív gráfnak több formája eltérő, de jelentésükben azonos. Feltételezzük, hogy a gráf irányítatlan, összefüggő és korlátos. A definíció a gráf csúcsai közötti távolság és a gráf automorfizmus fogalmát használja : $\Gamma =(V,E)$

A gráf két csúcsa közötti távolság a és a legrövidebb út mentén lévő élek száma $d(u,v)$ $u,v\in V(\Gamma )$ $\Gamma =(V,E)$ $u$ $v$
A gráf automorfizmus a gráf csúcsainak halmazának egy az egyhez leképezése önmagára, megőrizve a csúcsok szomszédságát. $g:V\rightarrow V$
A gráf automorfizmus csoportja gráf automorfizmusok halmaza. $\mathrm {Aut} (\Gamma )$

Godzilla-Royle definíció [1] Egy irányítatlan, összefüggő, korlátos gráfot távolságtranzitívnak mondunk , ha bármely két rendezett csúcspárra, és létezik olyan gráfautomorfizmus ,

\Gamma =(V,E)

(u,v)

(x,y)

d(u,v)=d(x,y)

g

\Gamma

g:(u,v)\jobbra (x,y)

Biggs-definíció [2] [3] Legyen egy irányítatlan, összefüggő, korlátos gráfnak egy automorfizmuscsoportja . Egy gráfot távolságtranzitívnak mondunk, ha minden olyan csúcsra , ahol létezik egy automorfizmus , amely leképezi és

\Gamma =(V,E)

\mathrm {Aut} (\Gamma )

\Gamma

u,v,x,y

d(u,v)=d(x,y)

g\in G

u\rightarrow x

v\rightarrow y

Definíció Ivanov-Ivanov-Faradzhev szerint [4] Egy irányítatlan összekapcsolt véges gráfot hurkok és több él nélkül távolságtranzitívnak mondunk, ha az automorfizmuscsoportja tranzitív módon hat egyenlő távolságra lévő csúcsok rendezett párjaira.

\Gamma =(V,E)

\mathrm {Aut} (\Gamma )

Definíció Cowan szerint [5] Legyen egy összefüggő átmérőgráf , és legyen az automorfizmus csoportja. távolság-tranzitív , ha minden halmazon tranzitív , ahol . Egy gráf távolságtranzitív, ha az automorfizmuscsoportja távolságtranzitív rajta.

\Gamma =(V,E)

D

\mathrm {Aut} (\Gamma )

\mathrm {Aut} (\Gamma )

\Gamma

{\displaystyle \Gamma _{i}=\left\{(x,y)\in \Gamma \times \Gamma :d(x,y)=i\jobbra\))

i=0,\,1,\,\ldots ,\,D

\Gamma

\mathrm {Aut} (\Gamma )

Definíció Ivanov szerint [6] Legyen egy irányítatlan, összefüggő, korlátos gráfnak egy automorfizmuscsoportja . Legyen egy alcsoport . Egy gráfot -távolság -tranzitívnak nevezünk , ha minden négy csúcsra van olyan automorfizmus , amely leképezi és -t . Egy gráfot távolság-tranzitívnak nevezünk, ha -távolság-tranzitív a gráf automorfizmuscsoportjának valamelyik alcsoportjára .

\Gamma =(V,E)

\mathrm {Aut} (\Gamma )

G

\mathrm {Aut} (\Gamma )

\Gamma

G

G

u,v,x,y

d(u,v)=d(x,y)

g\in G

u\rightarrow x

v\rightarrow y

G

G

Más szavakkal, van egy -távolság-tranzitív gráf, ha az alcsoport tranzitív módon hat minden egyes halmazra .

\Gamma

G

G

{\displaystyle \left\{(x,y)\mid x,e\in V(\Gamma ),\,d(x,y)=i\right\))

én

Kereszteződések tömbje

Legyen egy irányítatlan, összefüggő, korlátos gráf, amelynek két csúcsa távolságra van egymástól. A csúcsra eső összes csúcs három halmazra osztható , és a csúcstól való távolságuktól függően : $\Gamma =(V,E)$ $u,v\in V(\Gamma )$ ${\megjelenítési stílus j=d(u,v)}$ $w$ $u$ $A$ $B$ $C$ $d(v,w)$ $v$

{\displaystyle \left\{w\in A\colon d(v,w)=j\right\))

, , .

{\displaystyle \left\{w\in B\colon d(v,w)=j+1\right\))

{\displaystyle \left\{w\in C\colon d(v,w)=j-1\right\))

Ha a gráf távolságtranzitív, akkor a halmazok hatványai (bíborszámai) nem a csúcsoktól , hanem csak a távolságtól függenek, és metszésszámoknak nevezzük . $\Gamma$ $a_{j}=|A|,\,b_{j}=|B|,\,c_{j}=|C|$ $u,v$ ${\megjelenítési stílus j=d(u,v)}$

A kereszteződések számainak halmaza

\iota (\Gamma )={\begin{Bmatrix}\ast &c_{1}&c_{2}&\dots &c_{d-1}&c_{d}\\a_{0}&a_{1}&a_ {2}&\pontok &a_{d-1}&a_{d}\\b_{0}&b_{1}&b_{2}&\pontok &b_{d-1}&\ast \\\end{Bmátrix}}

távolságtranzitív gráf metszésponti tömbjének nevezzük [7] [8] .

Tulajdonságok

Minden távolság-tranzitív gráf távolságszabályos , de ennek fordítva nem igaz [4] [9] [10] [11] .
A távolság-tranzitív gráf csúcstranzitív és szimmetrikus [3] .
Fokú távolság-szabályos gráf metszéspontjainak tömbje $k$ . Mivel a távolság-tranzitív gráf szabályos, ezért a metszéspontszámok és . Sőt, . Ezért egy távolságszabályos gráf metszésponti tömbje a következőképpen írható fel: [4] [7] [8] : $b_{0}=k$ $c_{1}=1$ $a_{i}+b_{i}+c_{i}=k$

\iota (\Gamma )={\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{d-1}\,;\,1,\,c_{2 },\,\pontok ,\,c_{d}\end{Bmátrix}}

Példák

A távolság-tranzitív gráfok legegyszerűbb példái [5] [12] [13] :

komplett grafikonok $K_n$
komplett kétrészes gráfok (biclikek) egyenlő részekkel $K_{{n,n}}$
hiperkocka grafikonok $Q_{n}$

Bonyolultabb példák távolságtranzitív gráfokra:

Johnson gróf [14]
Grassmann-gráf [15]
Hamming grófja [16] [17]
Earl of Livingston [18]

Távolságszabályos és távolság-tranzitív grafikonok

Első pillantásra a távolság-tranzitív gráf és a távolság-reguláris gráf nagyon közeli fogalmak. Valójában minden távolság-tranzitív gráf távolságszabályos. A természetük azonban más. Ha egy távolság-tranzitív gráfot a gráf szimmetriája alapján határozunk meg az automorfizmus feltételén keresztül, akkor a távolság-reguláris gráfot a kombinatorikus szabályszerűségének feltételéből határozzuk meg [19] .

A távolság-tranzitív gráf csúcstranzitív, és metszéspontszámok vannak definiálva hozzá . Távolság-szabályos gráf esetén a metszéspontszámok is a kombinatorikus szabályosság alapján vannak meghatározva. Egy gráf távolság-tranzitivitása magában foglalja a távolság-szabályszerűségét, de ennek fordítva nem igaz [10] . Ezt 1969-ben, még a „távolság-tranzitív gráf” kifejezés bevezetése előtt bebizonyította szovjet matematikusok egy csoportja ( G. M. Adelson-Velsky , B. Yu. Veisfeler , A. A. Leman, I. A. Faradzhev) [20] [10] . A legkisebb távolság-reguláris gráf, amely nem távolságtranzitív, a Shrikhande gráf . Az egyetlen ilyen típusú háromértékű gráf a Tatta-féle 12 cellás gráf, amely 126 csúcsból áll [10] .

Távolság-tranzitív gráfok osztályozása

Az első általános eredményt a távolság-tranzitív gráfok osztályozásában Biggs és Smith [21] érte el 1971-ben, ahol a harmadik fokozatú gráfokat osztályozták. A következő tíz-tizenöt évben a távolság-tranzitív gráfok tanulmányozásának központi problémája a kis fokos távolság-tranzitív gráfok osztályozása volt [22] . A negyedik fokú távolság-tranzitív gráfokat Smith teljesen osztályozta [23] [24] .

1983-ban Cameron, Prager, Saxl és Seitz [25] és egymástól függetlenül 1985-ben Weiss [26] bebizonyította, hogy minden kettőnél nagyobb hatványra korlátozott számú távolság-tranzitív gráf létezik [27] .

Köbös távolság-tranzitív gráfok osztályozása

1971-ben N. Biggs és D. Smith bebizonyította azt a tételt, hogy a köbös (trivalens) gráfok között pontosan 12 távolság-tranzitív gráf található [21] :

Gróf név	Csúcsok száma	Átmérő	Heveder	Metszéspont tömb
Teljes gráf K 4	négy	egy	3	{3;1}
Teljes kétrészes gráf K 3,3	6	2	négy	{3,2;1,3}
Hiperkocka grafikon $Q_{3}$	nyolc	3	négy	{3,2,1;1,2,3}
Petersen grófja	tíz	2	5	{3,2;1,1}
Heawood grófja	tizennégy	3	6	{3,2,2;1,1,3}
Pappa gróf	tizennyolc	négy	6	{3,2,2,1;1,1,2,3}
dodekaéder gráf	húsz	5	5	{3,2,1,1,1;1,1,1,2,3}
Desargues gróf	húsz	5	6	{3,2,2,1,1;1,1,2,2,3}
Coxeter grófja	28	négy	7	{3,2,2,1;1,1,1,2}
Thatta-Coxeter grófja	harminc	négy	nyolc	{3,2,2,2;1,1,1,3}
Foster grófja	90	nyolc	tíz	{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}
Biggs-Smith grófja	102	7	9	{3,2,2,2,1,1,1;1,1,1,1,1,1,3}

Háromnál nagyobb fokú távolság-tranzitív grafikonok

Minden távolság-tranzitív fokgráf ismert [28] . A négyes fokozat (valencia) összes távolság-tranzitív grafikonját ( ) D. Smith készítette 1973-74-ben [23] [24] , az ötödik, hatodik és hetedik fokot 1984-ben A. A. Ivanov, A. V. Ivanov és I. A. Faradzhev [ 29] . $k<13$ $k=4$

1986-ban A. A. Ivanov és A. V. Ivanov megkapta az összes távolság-tranzitív grafikont a tól -ig terjedő fokokkal [30] . $k=8$ $k=13$

Az osztályozás megközelítései

Egyetlen csúcs stabilizátorának és a gráfátmérőt korlátozó tételeknek a figyelembevételén alapuló megközelítés keretében kaptuk meg a kis fokos távolság-tranzitív gráfok listáját. A. A. Ivanov ezt a megközelítést "helyinek" nevezte. A „globális” megközelítés az automorfizmus csoportnak a csúcsok halmazán gyakorolt hatásán alapul . Ez a megközelítés lehetővé teszi olyan távolság-tranzitív gráfok osztályozását, amelyeken egy csoport tevékenysége primitív. Ezekből épül fel az összes többi [22] .

Jegyzetek

↑ Godsil és Royle, 2001 , p. 66.
↑ Biggs, 1971 , p. 87.
↑ 1 2 Biggs, 1993 , p. 118.
↑ 1 2 3 Ivanov, Ivanov és Faradzhev, 1984 , p. 1704.
↑ 12. Cohen , 2004 , p. 223.
↑ Ivanov, 1994 , p. 285.
↑ 1 2 Lauri és Scapelatto, 2016 , p. 33.
↑ 1 2 Biggs, 1993 , p. 157.
↑ Lauri és Scapelatto, 2016 , p. 34.
↑ 1 2 3 4 Brouwer, Cohen és Neumaier, 1989 , p. 136.
↑ Cohen, 2004 , p. 232.
↑ Godsil és Royle, 2001 , p. 66-67.
↑ Biggs, 1993 , p. 158.
↑ Brouwer, Cohen és Neumaier 1989 , p. 255.
↑ Brouwer, Cohen és Neumaier 1989 , p. 269.
↑ Van Bon, 2007 , p. 519.
↑ Brouwer, Cohen és Neumaier 1989 , p. 261.
↑ Weisstein, Eric W. Livingstone Graph a Wolfram MathWorld weboldalán .
↑ Biggs, 1993 , p. 159.
↑ Adelson-Velsky, Weisfeler, Leman és Faradzhev, 1969 .
↑ 12 Biggs és Smith, 1971 .
↑ 1 2 Ivanov, 1994 , pp. 288-292.
↑ 12 Smith , 1973 .
↑ 12 Smith , 1974 .
↑ Cameron PJ, Praeger CE, Saxl J. és Seitz GM On the Sims sejtés és távolság-tranzitív grafikonok // Bull. London Math. szoc. - 1983. - 1. évf. 15. - P. 499-506.
↑ Weiss R. A távolság-tranzitív gráfokról // Bull. London Math. szoc. - 1985. - 1. évf. 17. - P. 253-256.
↑ Brouwer, Cohen és Neumaier 1989 , p. 214.
↑ Brouwer, Cohen és Neumaier 1989 , p. 221-225.
↑ Ivanov, Ivanov és Faradzsev, 1984 .
↑ Ivanov és Ivanov, 1988 .

Irodalom

Könyvek

Biggs N. Távolság-tranzitív gráfok // Automorfizmusok véges csoportjai (eng.) . - London és New York: Cambridge University Press, 1971. - 1. évf. 6. - P. 86-96. — (Londoni Mathematical Society Lecture Note Series).

Biggs NL távolság-tranzitív grafikonok // Algebrai gráfelmélet (angol) . — 2. kiadás. - Cambridge University Press, 1993. - P. 155-163. — 205 p.

Brouwer AE, Cohen AM, Neumaier A. Távolság - Tranzitív grafikonok // Távolság-reguláris grafikonok . - New York: Springer-Verlag, 1989. - P. 214-234.

Cohen AM Távolság-tranzitív gráfok // Témák az algebrai gráfelméletben / szerkesztette: LW Beineke, RJ Wilson. - Cambridge University Press, 2004. - Vol. 102. - P. 222-249. - (Matematika enciklopédiája és alkalmazásai).

Godsil C., Royle G. Távolság-tranzitív gráfok // Algebrai gráfelmélet (angol) . - New York: Springer-Verlag, 2001. - Vol. 207. - P. 66-69. — (Matematika diplomás szövegei). - doi : 10.1007/978-1-4613-0163-9 .
Ivanov AA, Ivanov AV Distance-transitive graphs of valency k , 8 < k < 13 // Algebraic, Extremal and Metric Combinatorics 1986 (angol) / Deza, M., Frankl, P., & Rosenberg, I. (szerk.) . - Cambridge: Cambridge University Press, 1988. - P. 112-145. — (Londoni Mathematical Society Lecture Note Series). - doi : 10.1017/CBO9780511758881 .

Ivanov AA Distance-Transitive Graphs and Their Classification (angol) // Faradžev IA, Ivanov AA, Klin MH, Woldar AJ (eds.) Investigations in Algebraic Theory of Combinatorial Objects. Matematika és alkalmazásai (Szovjet sorozat). - Dordrecht: Springer , 1994. - 1. évf. 84 . - P. 283-378 . - doi : 10.1007/978-94-017-1972-8 .
Lauri J. , Scapelatto R. Gráfautomorfizmusok és rekonstrukció témái . — 2. kiadás. - Cambridge: Cambridge University Press, 2016. - 188 p. — (Londoni Mathematical Society Lecture Note Series). - doi : 10.1017/CBO9781316669846 .

Cikkek

Adelson-Velsky G. M., Veisfeler B. Yu., Leman A. A., Faradzhev I. A. Egy olyan gráf példáján, amely nem rendelkezik tranzitív automorfizmus csoporttal // A Tudományos Akadémia jelentései . - 1969. - T. 185 , 5. sz . - S. 975-976 .
Ivanov A. A., Ivanov A. V., Faradzhev I. A. 5., 6. és 7. fokozatú távolságtranzitív gráfok // Zh. Vychisl. matematika. és mat. fizikai _ - 1984. - T. 24 , 11. sz . - S. 1704-1718 .
Biggs NL, Smith DH A trivalens gráfokról // Bulletin of the London Mathematical Society. - 1971. - 1. évf. 3 , iss. 2 . - 155-158 . o . - doi : 10.1112/blms/3.2.155 .
Smith DH A négyértékű gráfokon // J. Lodon Math. szoc. - 1973. - 1. évf. 6 . - P. 659-662 .
Smith DH A négyes vegyérték távolság-tranzitív grafikonjai // J. Lodon Math. szoc. - 1974. - 1. évf. 8 . - P. 377-384 .
Van Bon J. Véges primitív távolság-tranzitív gráfok (angol) // European Journal of Combinatorics. - 2007. - Vol. 28 , iss. 2 . - P. 517-532 . - doi : 10.1016/j.ejc.2005.04.014 .

Linkek

Weisstein, Eric W. Distance-Transitive Graph (angol) a Wolfram MathWorld webhelyén .