Vzdálenost-tranzitivní graf

Vzdálenost - přechodný graf je graf , ve kterém je jakákoli uspořádaná dvojice vrcholů přeložena do jakékoli jiné uspořádané dvojice vrcholů se stejnou vzdáleností mezi vrcholy jedním z automorfismů grafu .

Blízký koncept je vzdálenost-regulární graf , ale jejich povaha je odlišná. Je-li vzdálenostně-tranzitivní graf definován ze symetrie grafu přes podmínku automorfismu, pak je vzdálenostně-regulární graf definován z podmínky jeho kombinatorické pravidelnosti. Každý graf přechodu na vzdálenost je regulární na vzdálenost, ale obráceně to neplatí. To bylo prokázáno v roce 1969, ještě předtím, než byl vytvořen termín „vzdáleně-tranzitivní graf“.

Vzdálenost-regulární grafy stupňů menší než 13 jsou zcela klasifikovány.

Definice vzdálenostně-tranzitivního grafu

Existuje několik definic vzdálenostně-tranzitivního grafu, které se liší ve formě, ale mají stejný význam. Předpokládá se, že graf je neorientovaný, spojený a ohraničený. Definice používá koncepty vzdálenosti mezi vrcholy grafu a automorfismu grafu : $\Gamma =(V,E)$

Vzdálenost mezi dvěma vrcholy grafu je počet hran podél nejkratší cesty spojující a $d(u,v)$ $u,v\in V(\Gamma )$ $\Gamma =(V,E)$ $u$ $proti$
Automorfismus grafu je mapování množiny vrcholů grafu jedna ku jedné na sebe, přičemž se zachovává sousedství vrcholů. $g:V\rightarrow V$
Skupina automorfismu grafu je množina automorfismů grafu. $\mathrm {Aut} (\Gamma )$

Godzilla-Royle definice [1] Neorientovaný, spojený, ohraničený graf se nazývá vzdálenostně tranzitivní, pokud pro jakékoli dva uspořádané páry jeho vrcholů existuje takový automorfismus grafu , že

\Gamma =(V,E)

(u,v)

(x,y)

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

G

\Gamma

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

Biggsova definice [2] [3] Nechť neorientovaný, souvislý, ohraničený graf má grupu automorfismu . O grafu se říká, že je tranzitivní na vzdálenost, pokud pro všechny vrcholy existuje takový , že existuje automorfismus , který mapuje a

\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

Definice podle Ivanova-Ivanova-Faradzheva [4] Neorientovaný souvislý konečný graf bez smyček a násobných hran se nazývá vzdálenostně tranzitivní, pokud jeho skupina automorfismu tranzitivně působí na uspořádané dvojice ekvidistantních vrcholů.

\Gamma =(V,E)

\mathrm {Aut} (\Gamma )

Definice podle Cowana [5] Nechť je graf souvislého průměru a je jeho grupa automorfismu. je vzdálenostně tranzitivní on , pokud je tranzitivní na každé množině , kde . Graf je vzdálenostně tranzitivní, pokud je na něm jeho skupina automorfismu vzdálenostně tranzitivní.

\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\right\))

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

\Gamma

\mathrm {Aut} (\Gamma )

Definice podle Ivanova [6] Nechť neorientovaný, souvislý, ohraničený graf má grupu automorfismu . Nechť existuje podskupina . Graf se nazývá -vzdálenost -tranzitivní , pokud pro každé čtyři vrcholy takové , že existuje automorfismus , který mapuje a . Graf se nazývá vzdálenostně tranzitivní, pokud je -vzdáleně tranzitivní pro nějakou podgrupu skupiny automorfismu grafu.

\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

Jinými slovy, existuje -vzdáleně-tranzitivní graf, pokud podskupina působí tranzitivně na množinu pro každý .

\Gamma

G

G

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

i

Pole křižovatek

Nechť existuje neorientovaný, souvislý, ohraničený graf a dva jeho vrcholy jsou od sebe vzdálené. Všechny vrcholy spadající do vrcholu lze rozdělit do tří sad a v závislosti na jejich vzdálenosti od vrcholu : $\Gamma =(V,E)$ $u,v\in V(\Gamma )$ $j=d(u,v)$ $w$ $u$ $A$ $B$ $C$ $d(v,w)$ $proti$

\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\))

Pokud je graf vzdálenostně tranzitivní, pak mocniny (hlavní čísla) množin nezávisí na vrcholech , ale závisí pouze na vzdálenosti a nazývají se průsečíková čísla . $\Gamma$ $a_{j}=|A|,\,b_{j}=|B|,\,c_{j}=|C|$ $u,v$ $j=d(u,v)$

Sada čísel křižovatek

\iota (\Gamma )={\begin{Bmatrix}\ast &c_{1}&c_{2}&\tečky &c_{d-1}&c_{d}\\a_{0}&a_{1}&a_ {2}&\tečky &a_{d-1}&a_{d}\\b_{0}&b_{1}&b_{2}&\tečky &b_{d-1}&\ast \\\end{Bmatrix}}

se nazývá pole průniku vzdálenostně tranzitivního grafu [7] [8] .

Vlastnosti

Každý graf přechodu na vzdálenost je regulární na vzdálenost , ale obráceně to neplatí [4] [9] [10] [11] .
Vzdálenost-tranzitivní graf je vertex-tranzitivní a symetrický [3] .
Pole průsečíků vzdálenostně-regulárního grafu stupně $k$ . Vzhledem k tomu, že graf vzdálenost-tranzitivní je pravidelný, jsou čísla průsečíků a . Navíc, . Proto pole průniku vzdálenostně-regulárního grafu lze zapsat jako [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 },\,\tečky ,\,c_{d}\end{Bmatrix}}

Příklady

Nejjednodušší příklady vzdálenostně tranzitivních grafů [5] [12] [13] :

kompletní grafy $K_n$
kompletní bipartitní grafy (bicliques) se stejnými částmi $K_{{n,n}}$
hyperkrychlové grafy $Q_{n}$

Složitější příklady vzdálenostně tranzitivních grafů:

hrabě Johnson [14]
Grassmannův graf [15]
hrabě Hamming [16] [17]
hrabě z Livingstonu [18]

Vzdálenost-regulární a vzdálenost-tranzitivní grafy

Na první pohled jsou vzdálenostně-tranzitivní graf a vzdálenostně-regulární graf velmi blízké pojmy. Ve skutečnosti je každý graf procházející vzdáleností regulární. Jejich povaha je však odlišná. Je-li vzdálenostně tranzitivní graf definován na základě symetrie grafu prostřednictvím podmínky automorfismu, pak je vzdálenostně regulární graf definován z podmínky jeho kombinatorické pravidelnosti [19] .

Vzdáleně tranzitivní graf je vertexově tranzitivní a jsou pro něj definována čísla průsečíků . Pro vzdálenostně-regulární graf jsou čísla průsečíků také definována z hlediska kombinatorické pravidelnosti. Vzdálenost-tranzitivita grafu implikuje jeho vzdálenost-pravidelnost, ale obráceně to neplatí [10] . To bylo prokázáno v roce 1969, ještě před zavedením pojmu „vzdáleně-tranzitivní graf“, skupinou sovětských matematiků ( G. M. Adelson-Velsky , B. Yu. Veisfeler , A. A. Leman, I. A. Faradzhev) [20] [10] . Nejmenší vzdálenost-regulární graf, který není vzdálenost-tranzitivní je Shrikhande graf . Jediným trivalentním grafem tohoto typu je Tattův 12-buňkový graf se 126 vrcholy [10] .

Klasifikace vzdálenostně tranzitivních grafů

První obecný výsledek v klasifikaci vzdálenostně tranzitivních grafů získali Biggs a Smith [21] v roce 1971, kde byly klasifikovány grafy třetího stupně. Během následujících deseti až patnácti let byla hlavním problémem studia grafů s přechodem na vzdálenost klasifikace grafů s přechodem na vzdálenost malých stupňů [22] . Vzdálenost-tranzitivní grafy stupně čtyři byly kompletně klasifikovány Smithem [23] [24] .

V roce 1983 Cameron, Prager, Saxl a Seitz [25] a nezávisle v roce 1985 Weiss [26] dokázali, že pro každou mocninu větší než dva existuje omezený počet grafů s přechodem vzdálenosti [27] .

Klasifikace kubických vzdálenostně-tranzitivních grafů

V roce 1971 N. Biggs a D. Smith dokázali větu, že mezi kubickými (trivalentními) grafy existuje přesně 12 vzdálenostně tranzitivních grafů [21] :

Jméno počítání	Počet vrcholů	Průměr	obvod	Pole křižovatek
Kompletní graf K 4	čtyři	jeden	3	{3;1}
Kompletní bipartitní graf K 3,3	6	2	čtyři	{3,2;1,3}
Hyperkrychlový graf $Q_{3}$	osm	3	čtyři	{3,2,1;1,2,3}
hrabě z Petersenu	deset	2	5	{3,2;1,1}
hrabě z Heawood	čtrnáct	3	6	{3,2,2;1,1,3}
hrabě Pappa	osmnáct	čtyři	6	{3,2,2,1;1,1,2,3}
dvanáctistěnný graf	dvacet	5	5	{3,2,1,1,1;1,1,1,2,3}
hrabě Desargues	dvacet	5	6	{3,2,2,1,1;1,1,2,2,3}
hrabě z Coxeter	28	čtyři	7	{3,2,2,1;1,1,1,2}
Hrabě z Thatta-Coxeter	třicet	čtyři	osm	{3,2,2,2;1,1,1,3}
hrabě z Foster	90	osm	deset	{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}
hrabě z Biggs-Smith	102	7	9	{3,2,2,2,1,1,1;1,1,1,1,1,1,3}

Distančně-tranzitivní grafy stupně většího než tři

Všechny vzdálenostně-tranzitivní stupňové grafy jsou známy [28] . Všechny vzdálenostně tranzitivní grafy stupně (valence) čtyři ( ) získal D. Smith v letech 1973-74 [23] [24] , pátý, šestý a sedmý stupeň v roce 1984 A. A. Ivanov, A. V. Ivanov a I. A. Faradzhev [ 29] . $k<13$ $k=4$

V roce 1986 A. A. Ivanov a A. V. Ivanov získali všechny vzdálenostně tranzitivní grafy stupňů od do [30] . $k=8$ $k=13$

Přístupy ke klasifikaci

Seznamy vzdálenostně tranzitivních grafů malých stupňů byly získány v rámci přístupu založeného na uvažování stabilizátoru jednoho vrcholu a teorémů, které omezují průměr grafu. A. A. Ivanov nazval tento přístup „místním“. „Globální“ přístup je založen na zvažování působení grupy automorfismu na množinu vrcholů. Tento přístup umožňuje klasifikovat vzdálenostně tranzitivní grafy, na kterých je akce grupy primitivní. Z nich se pak konstruuje vše ostatní [22] .

Poznámky

↑ Godsil a Royle, 2001 , str. 66.
↑ Biggs, 1971 , str. 87.
↑ 1 2 Biggs, 1993 , str. 118.
↑ 1 2 3 Ivanov, Ivanov a Faradzhev, 1984 , s. 1704.
↑ 12 Cohen , 2004 , str. 223.
↑ Ivanov, 1994 , s. 285.
↑ 1 2 Lauri a Scapelatto, 2016 , str. 33.
↑ 1 2 Biggs, 1993 , str. 157.
↑ Lauri a Scapelatto, 2016 , str. 34.
↑ 1 2 3 4 Brouwer, Cohen a Neumaier, 1989 , s. 136.
↑ Cohen, 2004 , str. 232.
↑ Godsil a Royle, 2001 , str. 66-67.
↑ Biggs, 1993 , str. 158.
↑ Brouwer, Cohen a Neumaier 1989 , s. 255.
↑ Brouwer, Cohen a Neumaier 1989 , s. 269.
↑ Van Bon, 2007 , str. 519.
↑ Brouwer, Cohen a Neumaier 1989 , s. 261.
↑ Weisstein, Eric W. Livingstone Graph na webu Wolfram MathWorld .
↑ Biggs, 1993 , str. 159.
↑ Adelson-Velsky, Weisfeler, Leman a Faradzhev, 1969 .
↑ 12 Biggs a Smith, 1971 .
↑ 1 2 Ivanov, 1994 , pp. 288-292.
↑ 12 Smith , 1973 .
↑ 12 Smith , 1974 .
↑ Cameron PJ, Praeger CE, Saxl J. a Seitz GM O domněnkách The Sims a grafech tranzitivních vzdáleností // Bull. Londýnská matematika. soc. - 1983. - Sv. 15. - S. 499-506.
↑ Weiss R. O grafech s přechodem na vzdálenost // Bull. Londýnská matematika. soc. - 1985. - Sv. 17. - S. 253-256.
↑ Brouwer, Cohen a Neumaier 1989 , s. 214.
↑ Brouwer, Cohen a Neumaier 1989 , s. 221-225.
↑ Ivanov, Ivanov a Faradzhev, 1984 .
↑ Ivanov a Ivanov, 1988 .

Literatura

knihy

Biggs N. Distance-Transitive Graphs // Finite Groups of Automorphisms (angl.) . - Londýn a New York: Cambridge University Press, 1971. - Sv. 6. - S. 86-96. — (London Mathematical Society Lecture Note Series).

Biggs NL Distance-Transitive Graphs // Algebraic Graph Theory (anglicky) . — 2. vydání. - Cambridge University Press, 1993. - S. 155-163. — 205 str.

Brouwer AE, Cohen AM, Neumaier A. Distance - Transitive Graphs // Distance-Regular Graphs . - New York: Springer-Verlag, 1989. - S. 214-234.

Cohen AM Distance-transitive graphs // Topics in Algebraic Graph Theory / edited by LW Beineke, RJ Wilson. - Cambridge University Press, 2004. - Sv. 102. - S. 222-249. - (Encyklopedie matematiky a její aplikace).

Godsil C., Royle G. Distance-Transitive Graphs // Algebraic Graph Theory (anglicky) . - New York: Springer-Verlag, 2001. - Sv. 207. - S. 66-69. — (Absolventské texty z matematiky). - doi : 10.1007/978-1-4613-0163-9 .
Ivanov AA, Ivanov AV Distančně-tranzitivní grafy valence k , 8 < k < 13 // Algebraická, extremální a metrická kombinatorika 1986 (anglicky) / Deza, M., Frankl, P., & Rosenberg, I. (Eds.) . - Cambridge: Cambridge University Press, 1988. - S. 112-145. — (London Mathematical Society Lecture Note Series). - doi : 10.1017/CBO9780511758881 .

Ivanov AA Distance-Transitive Graphs and their Classification (anglicky) // Faradžev IA, Ivanov AA, Klin MH, Woldar AJ (eds.) Investigations in Algebraic Theory of Combinatorial Objects. Matematika a její aplikace (sovětská řada). - Dordrecht: Springer , 1994. - Sv. 84 . - str. 283-378 . - doi : 10.1007/978-94-017-1972-8 .
Lauri J. , Scapelatto R. Témata grafových automorfismů a rekonstrukce . — 2. vydání. - Cambridge: Cambridge University Press, 2016. - 188 s. — (London Mathematical Society Lecture Note Series). - doi : 10.1017/CBO9781316669846 .

články

Adelson-Velsky G. M., Veisfeler B. Yu., Leman A. A., Faradzhev I. A. Na příkladu grafu, který nemá tranzitivní skupinu automorfismu // Zprávy Akademie věd . - 1969. - T. 185 , č. 5 . - S. 975-976 .
Ivanov A. A., Ivanov A. V., Faradzhev I. A. Distančně-tranzitivní grafy stupně 5, 6 a 7 // Zh. Vychisl. matematika. a mat. fyzický _ - 1984. - T. 24 , č. 11 . - S. 1704-1718 .
Biggs NL, Smith DH O trivalentních grafech // Bulletin of the London Mathematical Society. - 1971. - Sv. 3 , iss. 2 . - S. 155-158 . - doi : 10.1112/blms/3.2.155 .
Smith DH Na čtyřvalentních grafech // J. Lodon Math. soc. - 1973. - Sv. 6 . - S. 659-662 .
Smith DH Vzdálenostně-tranzitivní grafy valence čtyři // J. Lodon Math. soc. - 1974. - Sv. 8 . - str. 377-384 .
Van Bon J. Konečné primitivní grafy přechodu vzdálenosti (anglicky) // European Journal of Combinatorics. - 2007. - Sv. 28 , iss. 2 . - str. 517-532 . - doi : 10.1016/j.ejc.2005.04.014 .

Odkazy

Weisstein, Eric W. Distance-Transitive Graph (anglicky) na webových stránkách Wolfram MathWorld .