Graficul distanță-tranzitiv

Un graf tranzitiv de distanță este un graf în care orice pereche ordonată de vârfuri este translată în orice altă pereche ordonată de vârfuri cu aceeași distanță între vârfuri de către unul dintre automorfismele grafului .

Un concept apropiat este un grafic distanță-regulat , dar natura lor este diferită. Dacă un graf distanță-tranzitiv este definit din simetria grafului prin condiția de automorfism, atunci un graf distanță-regular este definit din condiția regularității sale combinatorii. Fiecare grafic tranzitiv la distanță este regulat la distanță, dar inversul nu este adevărat. Acest lucru a fost dovedit în 1969, chiar înainte ca termenul „graf tranzitiv la distanță” să fie inventat.

Graficele distanțe-regulate de grade mai mici de 13 sunt complet clasificate.

Definiții ale unui grafic distanță-tranzitiv

Există mai multe definiții diferite ca formă, dar identice ca înțeles, ale unui graf tranzitiv la distanță. Se presupune că graficul este nedirecționat, conectat și mărginit. Definiția folosește conceptele de distanță dintre vârfurile grafului și automorfismul grafului : $\Gamma =(V,E)$

Distanța dintre două vârfuri ale unui grafic este numărul de muchii de-a lungul celei mai scurte căi care leagă și $d(u,v)$ $u,v\in V(\Gamma )$ $\Gamma =(V,E)$ $u$ $v$
Un automorfism de graf este o mapare unu-la-unu a setului de vârfuri ale unui graf pe el însuși, păstrând adiacența vârfurilor. $g:V\rightarrow V$
Un grup de automorfisme de graf este un set de automorfisme de graf. $\mathrm {Aut} (\Gamma )$

Definiția Godzilla-Royle [1] Un graf nedirecționat, conexat, mărginit se spune a fi tranzitiv la distanță dacă pentru oricare două perechi ordonate de vârfuri și astfel încât există un automorfism de graf astfel încât

\Gamma =(V,E)

(u,v)

(X y)

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

g

\Gamma

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

Definiția lui Biggs [2] [3] Fie un graf nedirecționat, conexat, mărginit să aibă un grup de automorfism . Se spune că un grafic este tranzitiv la distanță dacă pentru toate nodurile astfel încât , există un automorfism , care mapează și

\Gamma =(V,E)

\mathrm {Aut} (\Gamma )

\Gamma

u,v,x,y

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

g\în G

u\rightarrow x

v\rightarrow y

Definiție conform lui Ivanov-Ivanov-Faradzhev [4] Un graf finit conectat nedirecționat fără bucle și muchii multiple se spune că este tranzitiv la distanță dacă grupul său de automorfism acționează tranzitiv pe perechi ordonate de vârfuri echidistante.

\Gamma =(V,E)

\mathrm {Aut} (\Gamma )

Definiție conform lui Cowan [5] Fie un grafic cu diametrul conex și grupul său de automorfism. este tranzitiv la distanță pe dacă este tranzitiv pe fiecare mulțime , unde . Un grafic este tranzitiv la distanță dacă grupul său de automorfism este tranzitiv la distanță pe el.

\Gamma =(V,E)

D

\mathrm {Aut} (\Gamma )

\mathrm {Aut} (\Gamma )

\Gamma

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

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

\Gamma

\mathrm {Aut} (\Gamma )

Definiție după Ivanov [6] Fie un graf nedirecționat, conexat, mărginit să aibă un grup de automorfism . Să existe un subgrup . Un grafic se numește -distanță -tranzitiv dacă pentru fiecare patru vârfuri astfel încât , există un automorfism care mapează și . Un grafic se numește distanță-tranzitiv dacă este -distanță-tranzitiv pentru un subgrup al grupului de automorfism al grafului.

\Gamma =(V,E)

\mathrm {Aut} (\Gamma )

G

\mathrm {Aut} (\Gamma )

\Gamma

G

G

u,v,x,y

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

g\în G

u\rightarrow x

v\rightarrow y

G

G

Cu alte cuvinte, există un grafic -distanță-tranzitiv dacă subgrupul acționează tranzitiv asupra mulțimii pentru fiecare .

\Gamma

G

G

\stanga\{(x,y)\mid x,e\in V(\Gamma),\,d(x,y)=i\dreapta\)

i

Matrice de intersecții

Să existe un graf nedirecționat, conexat, mărginit, iar două dintre vârfurile sale sunt la o distanță unul de celălalt. Toate vârfurile incidente la vârf pot fi împărțite în trei seturi și în funcție de distanța lor până la vârf : $\Gamma =(V,E)$ $u,v\in V(\Gamma )$ $j=d(u,v)$ $w$ $u$ $A$ $B$ $C$ $d(v,w)$ $v$

\left\{w\în A\colon d(v,w)=j\right\)

, , .

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

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

Dacă graficul este tranzitiv la distanță, atunci puterile (numerele cardinale) ale mulțimilor nu depind de vârfuri , ci depind doar de distanță și se numesc numere de intersecție . $\Gamma$ $a_{j}=|A|,\,b_{j}=|B|,\,c_{j}=|C|$ $u,v$ $j=d(u,v)$

Set de numere de intersecție

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

se numește matrice de intersecție a unui grafic distanță-tranzitiv [7] [8] .

Proprietăți

Fiecare grafic distanță-tranzitiv este distanță-regular , dar inversul nu este adevărat [4] [9] [10] [11] .
Un grafic tranzitiv la distanță este tranzitiv la vârf și simetric [3] .
O matrice de intersecții ale unui grafic distanță-regular de grad $k$ . Deoarece graficul distanță-tranzitiv este regulat, numerele de intersecție și . Mai mult, . Prin urmare, matricea de intersecție a unui grafic distanță-regulată poate fi scrisă ca [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 },\,\dots ,\,c_{d}\end{Bmatrix}}

Exemple

Cele mai simple exemple de grafice tranzitive la distanță [5] [12] [13] :

grafice complete $K_n$
grafuri bipartite complete (bicliques) cu părți egale $K_{{n,n}}$
grafice hipercube $Q_{n}$

Exemple mai complexe de grafice tranzitive la distanță:

Contele Johnson [14]
Graficul Grassmann [15]
conte de Hamming [16] [17]
Contele de Livingston [18]

Grafice distanță-regulată și distanță-tranzitivă

La prima vedere, un grafic distanță-tranzitiv și un grafic distanță-regular sunt concepte foarte apropiate. Într-adevăr, fiecare grafic tranzitiv la distanță este regulat la distanță. Cu toate acestea, natura lor este diferită. Dacă un graf distanță-tranzitiv este definit pe baza simetriei grafului prin condiția de automorfism, atunci un graf distanță-regular este definit din condiția regularității sale combinatorii [19] .

Un grafic tranzitiv la distanță este tranzitiv la vârf, iar numerele de intersecție sunt definite pentru acesta . Pentru un grafic distanță-regular, numerele de intersecție sunt definite și în termeni de regularitate combinatorie. Distanța-tranzitivitatea unui grafic implică distanța-regularitatea acestuia, dar inversul nu este adevărat [10] . Acest lucru a fost dovedit în 1969, chiar înainte de introducerea termenului de „graf tranzitiv distanță”, de către un grup de matematicieni sovietici ( G. M. Adelson-Velsky , B. Yu. Veisfeler , A. A. Leman, I. A. Faradzhev ) [20] [10] . Cel mai mic grafic distanță-regular care nu este tranzitiv la distanță este graficul Shrikhande . Singurul grafic trivalent de acest tip este cel cu 12 celule al lui Tatta , un grafic cu 126 de vârfuri [10] .

Clasificarea graficelor distanță-tranzitive

Primul rezultat general în clasificarea graficelor distanță-tranzitive a fost obținut de Biggs și Smith [21] în 1971, unde au fost clasificate grafice de gradul trei. În următorii zece până la cincisprezece ani, problema centrală în studiul graficelor distanță-tranzitive a fost clasificarea graficelor distanță-tranzitive de grade mici [22] . Graficele distanță-tranzitive de gradul patru au fost complet clasificate de Smith [23] [24] .

În 1983 Cameron, Prager, Saxl și Seitz [25] și în mod independent în 1985 Weiss [26] au demonstrat că pentru orice putere mai mare de două există un număr limitat de grafice distanță-tranzitive [27] .

Clasificarea graficelor distanță cubică-tranzitivă

În 1971, N. Biggs și D. Smith au demonstrat teorema că printre graficele cubice (trivalente) există exact 12 grafice la distanță tranzitivă [21] :

Nume număr	Numărul de vârfuri	Diametru	Circumferinţă	Matrice de intersecție
Completați graficul K 4	patru	unu	3	{3;1}
Graficul bipartit complet K 3,3	6	2	patru	{3,2;1,3}
Graficul hipercubului $Q_{3}$	opt	3	patru	{3,2,1;1,2,3}
Contele de Petersen	zece	2	5	{3,2;1,1}
Contele de Heawood	paisprezece	3	6	{3,2,2;1,1,3}
Contele Pappa	optsprezece	patru	6	{3,2,2,1;1,1,2,3}
graficul dodecaedru	douăzeci	5	5	{3,2,1,1,1;1,1,1,2,3}
Contele Desargues	douăzeci	5	6	{3,2,2,1,1;1,1,2,2,3}
Contele de Coxeter	28	patru	7	{3,2,2,1;1,1,1,2}
Contele de Thatta-Coxeter	treizeci	patru	opt	{3,2,2,2;1,1,1,3}
Contele de Foster	90	opt	zece	{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}
Contele de Biggs-Smith	102	7	9	{3,2,2,2,1,1,1;1,1,1,1,1,1,3}

Grafice distanță-tranzitive de grad mai mare de trei

Toate graficele de grade tranzitive distanță sunt cunoscute [28] . Toate graficele tranzitive la distanță de gradul (valența) patru ( ) au fost obținute de D. Smith în 1973-74 [23] [24] , iar gradele cinci, șase și șapte în 1984 de A. A. Ivanov, A. V. Ivanov și I. A. Faradzhev [ 29] . $k<13$ $k=4$

În 1986, A. A. Ivanov și A. V. Ivanov au obținut toate graficele tranzitive la distanță de grade de la până la [30] . $k=8$ $k=13$

Abordări ale clasificării

Liste de grafice distanță-tranzitive de grade mici au fost obținute în cadrul unei abordări bazate pe luarea în considerare a stabilizatorului unui singur vârf și a teoremelor care limitează diametrul graficului. A. A. Ivanov a numit această abordare „locală”. Abordarea „globală” se bazează pe luarea în considerare a acțiunii grupului automorfism asupra mulțimii de vârfuri. Această abordare face posibilă clasificarea graficelor distanță-tranzitive pe care acțiunea unui grup este primitivă. Din ele se construiesc apoi toate celelalte [22] .

Note

↑ Godsil și Royle, 2001 , p. 66.
↑ Biggs, 1971 , p. 87.
↑ 1 2 Biggs, 1993 , p. 118.
↑ 1 2 3 Ivanov, Ivanov și Faradjev, 1984 , p. 1704.
↑ 12 Cohen , 2004 , p. 223.
↑ Ivanov, 1994 , p. 285.
↑ 1 2 Lauri și Scapelatto, 2016 , p. 33.
↑ 1 2 Biggs, 1993 , p. 157.
↑ Lauri și Scapelatto, 2016 , p. 34.
↑ 1 2 3 4 Brouwer, Cohen și Neumaier, 1989 , p. 136.
↑ Cohen, 2004 , p. 232.
↑ Godsil și Royle, 2001 , p. 66-67.
↑ Biggs, 1993 , p. 158.
↑ Brouwer, Cohen și Neumaier 1989 , p. 255.
↑ Brouwer, Cohen și Neumaier 1989 , p. 269.
↑ Van Bon, 2007 , p. 519.
↑ Brouwer, Cohen și Neumaier 1989 , p. 261.
^ Weisstein , Eric W. Livingstone Graph pe site- ul Wolfram MathWorld .
↑ Biggs, 1993 , p. 159.
↑ Adelson-Velsky, Weisfeler, Leman și Faradzhev, 1969 .
↑ 12 Biggs și Smith, 1971 .
↑ 1 2 Ivanov, 1994 , pp. 288-292.
↑ 12 Smith , 1973 .
↑ 12 Smith , 1974 .
↑ Cameron PJ, Praeger CE, Saxl J. și Seitz GM Despre conjectura Sims și graficele tranzitive la distanță // Bull. London Math. soc. - 1983. - Vol. 15. - P. 499-506.
↑ Weiss R. Despre graficele distanță-tranzitive // Bull. London Math. soc. - 1985. - Vol. 17. - P. 253-256.
↑ Brouwer, Cohen și Neumaier 1989 , p. 214.
↑ Brouwer, Cohen și Neumaier 1989 , p. 221-225.
↑ Ivanov, Ivanov și Faradjev, 1984 .
↑ Ivanov și Ivanov, 1988 .

Literatură

Cărți

Biggs N. Grafice distanță-tranzitive // Grupuri finite de automorfisme (ing.) . - Londra & New York: Cambridge University Press, 1971. - Vol. 6. - P. 86-96. — (London Mathematical Society Lecture Note Series).

Biggs NL Grafice tranzitive la distanță // Teoria graficelor algebrice (engleză) . — ediția a II-a. - Cambridge University Press, 1993. - P. 155-163. — 205p.

Brouwer AE, Cohen AM, Neumaier A. Distanță - Grafice tranzitive // Distanță- Grafice regulate . - New York: Springer-Verlag, 1989. - P. 214-234.

Cohen AM Grafe tranzitive la distanță // Subiecte în teoria graficelor algebrice / editat de LW Beineke, RJ Wilson. - Cambridge University Press, 2004. - Vol. 102. - P. 222-249. - (Enciclopedia Matematicii si aplicatiile sale).

Godsil C., Royle G. Grafice tranzitiv-distanță // Teoria graficelor algebrice (engleză) . - New York: Springer-Verlag, 2001. - Vol. 207. - P. 66-69. — (Texte de absolvire în matematică). - doi : 10.1007/978-1-4613-0163-9 .
Ivanov AA, Ivanov AV Grafice tranzitive la distanță ale valenței k , 8 < k < 13 // Combinatorică algebrică, extremă și metrică 1986 (engleză) / Deza, M., Frankl, P., & Rosenberg, I. (Eds. ) . - Cambridge: Cambridge University Press, 1988. - P. 112-145. — (London Mathematical Society Lecture Note Series). - doi : 10.1017/CBO9780511758881 .

Ivanov AA Grafice tranzitive la distanță și clasificarea lor (engleză) // Faradžev IA, Ivanov AA, Klin MH, Woldar AJ (eds.) Investigations in Algebraic Theory of Combinatorial Objects. Matematica și aplicațiile sale (seria sovietică). - Dordrecht: Springer , 1994. - Vol. 84 . - P. 283-378 . - doi : 10.1007/978-94-017-1972-8 .
Lauri J. , Scapelatto R. Topics in Graph Automorphisms and Reconstruction . — ediția a II-a. - Cambridge: Cambridge University Press, 2016. - 188 p. — (London Mathematical Society Lecture Note Series). - doi : 10.1017/CBO9781316669846 .

Articole

Adelson-Velsky G. M., Veisfeler B. Yu., Leman A. A., Faradzhev I. A. Pe un exemplu de grafic care nu are un grup de automorfism tranzitiv // Rapoarte ale Academiei de Științe . - 1969. - T. 185 , nr 5 . - S. 975-976 .
Ivanov A. A., Ivanov A. V., Faradzhev I. A. Grafice tranzitive la distanță de gradul 5, 6 și 7 // Zh. Vychisl. matematica. și mat. fizic _ - 1984. - T. 24 , nr 11 . - S. 1704-1718 .
Biggs NL, Smith DH Despre grafice trivalente // Buletinul Societății de Matematică din Londra. - 1971. - Vol. 3 , iss. 2 . - P. 155-158 . - doi : 10.1112/blms/3.2.155 .
Smith DH Despre grafuri tetravalente // J. Lodon Math. soc. - 1973. - Vol. 6 . - P. 659-662 .
Smith DH Grafice distanță-tranzitive de valență patru // J. Lodon Math. soc. - 1974. - Vol. 8 . - P. 377-384 .
Van Bon J. Finite primitive distance-tranzitive graphs (engleză) // European Journal of Combinatorics. - 2007. - Vol. 28 , iss. 2 . - P. 517-532 . - doi : 10.1016/j.ejc.2005.04.014 .

Link -uri

Weisstein, Eric W. Distance-Transitive Graph (engleză) pe site-ul Wolfram MathWorld .