Avståndstransitiv graf

En avståndstransitiv graf är en graf där ett ordnat par av hörn översätts till vilket annat ordnat par av hörn som helst med samma avstånd mellan hörn av en av grafens automorfismer .

Ett nära koncept är en avståndsregelbunden graf , men deras natur är annorlunda. Om en avståndstransitiv graf definieras från grafens symmetri genom automorfismtillståndet, definieras en avståndsreguljär graf från tillståndet för dess kombinatoriska regelbundenhet. Varje avståndstransitiv graf är avståndsregelbunden, men det omvända är inte sant. Detta bevisades 1969, redan innan termen "distanstransitiv graf" myntades.

Avståndsregelbundna grafer med grader mindre än 13 är helt klassificerade.

Definitioner av en distanstransitiv graf

Det finns flera olika i form, men identiska i betydelse, definitioner av en distanstransitiv graf. Grafen antas vara oriktad, ansluten och avgränsad. Definitionen använder begreppen avstånd mellan grafens hörn och grafautomorfism : $\Gamma =(V,E)$

Avståndet mellan två hörn av en graf är antalet kanter längs den kortaste vägen som förbinder och $d(u,v)$ $u,v\in V(\Gamma )$ $\Gamma =(V,E)$ $u$ $v$
En grafautomorfism är en en-till-en-mappning av uppsättningen av hörn i en graf på sig själv, vilket bevarar närliggande hörn. $g:V\rightarrow V$
En grafautomorfigrupp är en uppsättning grafautomorfismer. $\mathrm {Aut} (\Gamma )$

Godzilla-Royle definition [1] En oriktad, sammankopplad, avgränsad graf sägs vara avståndstransitiv om för två ordnade par av dess hörn och så att det existerar en grafautomorfism så att

\Gamma =(V,E)

(u,v)

(x,y)

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

g

\Gamma

g:(u,v)\högerpil (x,y)

Biggs definition [2] [3] Låt en oriktad, sammankopplad, avgränsad graf ha en automorfismgrupp . En graf sägs vara avståndstransitiv om det för alla hörn finns en automorfism som kartlägger och

\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

Definition enligt Ivanov-Ivanov-Faradzhev [4] En oriktad sammankopplad finit graf utan slingor och flera kanter sägs vara avståndstransitiv om dess automorfismgrupp verkar transitivt på ordnade par av ekvidistanta hörn

\Gamma =(V,E)

\mathrm {Aut} (\Gamma )

Definition enligt Cowan [5] Låt vara en sammankopplad diametergraf och vara dess automorfismgrupp. är avståndstransitiv på om den är transitiv på varje set , där . En graf är avståndstransitiv om dess automorfismgrupp är avståndstransitiv på den.

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

Definition enligt Ivanov [6] Låt en oriktad, sammankopplad, avgränsad graf ha en automorfismgrupp . Låt det finnas en undergrupp . En graf kallas -distans -transitiv om för varje fyra hörn så att , Det finns en automorfism som kartlägger och . En graf kallas avståndstransitiv om den är -distanstransitiv för någon undergrupp av grafens automorfismgrupp.

\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

Med andra ord, det finns en -distans-transitiv graf om undergruppen agerar transitivt på uppsättningen för varje .

\Gamma

G

G

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

i

Array av korsningar

Låt det finnas en oriktad, sammankopplad, avgränsad graf, och två av dess hörn är på avstånd från varandra. Alla hörn som träffar vertexen kan delas in i tre uppsättningar , och beroende på deras avstånd till vertexen : $\Gamma =(V,E)$ $u,v\in V(\Gamma )$ $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\))

Om grafen är avståndstransitiv, så beror inte styrkorna (kardinaltalen) av mängderna på hörnen , utan beror endast på avståndet och kallas skärningstal . $\Gamma$ $a_{j}=|A|,\,b_{j}=|B|,\,c_{j}=|C|$ $u,v$ $j=d(u,v)$

Uppsättning av korsningsnummer

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

kallas skärningsmatrisen för en distanstransitiv graf [7] [8] .

Egenskaper

Varje distanstransitiv graf är avståndsregelbunden , men det omvända är inte sant [4] [9] [10] [11] .
En distanstransitiv graf är vertextransitiv och symmetrisk [3] .
En matris av skärningspunkter för en avstånd-reguljär graf av grad $k$ . Eftersom den avståndstransitiva grafen är regelbunden, är skärningsnumren och . Dessutom ,. Därför kan skärningsmatrisen för en avstånd-reguljär graf skrivas som [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}}

Exempel

De enklaste exemplen på distanstransitiva grafer [5] [12] [13] :

kompletta grafer $K_n$
kompletta tvådelade grafer (bicliques) med lika delar $K_{{n,n}}$
hyperkubgrafer $Q_{n}$

Mer komplexa exempel på avståndstransitiva grafer:

Greve Johnson [14]
Grassmann-graf [15]
greve av Hamming [16] [17]
Earl of Livingston [18]

Avståndsreguljära och avståndstransitiva grafer

Vid första anblicken är en avståndstransitiv graf och en avståndsreguljär graf mycket nära begrepp. Faktum är att varje avståndstransitiv graf är avståndsregelbunden. Men deras natur är annorlunda. Om en avståndstransitiv graf definieras baserat på grafens symmetri genom automorfismtillståndet, definieras en avståndsreguljär graf utifrån villkoret för dess kombinatoriska regelbundenhet [19] .

En avståndstransitiv graf är vertextransitiv och korsningsnummer definieras för den . För en distans-reguljär graf definieras skärningsnumren också i termer av kombinatorisk regularitet. Avståndstransitivitet för en graf antyder dess avståndsregelbundenhet, men det omvända är inte sant [10] . Detta bevisades 1969, även innan termen "distanstransitiv graf" introducerades av en grupp sovjetiska matematiker ( G.M. Adelson-Velsky , B. Yu. Veisfeler , A.A. Leman, I.A. Faradzhev) [20] [10] . Den minsta avstånds-reguljära grafen som inte är avståndstransitiv är Shrikhande-grafen . Den enda trivalenta grafen av denna typ är Tattas 12-cell , en graf med 126 hörn [10] .

Klassificering av avståndstransitiva grafer

Det första allmänna resultatet i klassificeringen av distanstransitiva grafer erhölls av Biggs och Smith [21] 1971, där grafer av grad tre klassificerades. Under de kommande tio till femton åren var det centrala problemet i studiet av distanstransitiva grafer klassificeringen av distanstransitiva grafer av små grader [22] . Avståndstransitiva grafer av grad fyra klassificerades fullständigt av Smith [23] [24] .

År 1983 Cameron, Prager, Saxl och Seitz [25] och oberoende 1985 Weiss [26] bevisade att för varje effekt större än två finns det ett begränsat antal avståndstransitiva grafer [27] .

Klassificering av kubiska distanstransitiva grafer

År 1971 bevisade N. Biggs och D. Smith satsen att det bland kubiska (trivalenta) grafer finns exakt 12 avståndstransitiva grafer [21] :

Räkna namn	Antal hörn	Diameter	Omkrets	Intersection array
Komplett graf K 4	fyra	ett	3	{3;1}
Komplett tvådelad graf K 3,3	6	2	fyra	{3,2;1,3}
Hypercube graf $F_{3}$	åtta	3	fyra	{3,2,1;1,2,3}
Greve av Petersen	tio	2	5	{3,2;1,1}
Earl av Heawood	fjorton	3	6	{3,2,2;1,1,3}
Greve Pappa	arton	fyra	6	{3,2,2,1;1,1,2,3}
dodekaedergraf	tjugo	5	5	{3,2,1,1,1;1,1,1,2,3}
Greve Desargues	tjugo	5	6	{3,2,2,1,1;1,1,2,2,3}
Earl av Coxeter	28	fyra	7	{3,2,2,1;1,1,1,2}
Greve av Thatta-Coxeter	trettio	fyra	åtta	{3,2,2,2;1,1,1,3}
Earl of Foster	90	åtta	tio	{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}
Earl of Biggs-Smith	102	7	9	{3,2,2,2,1,1,1;1,1,1,1,1,1,3}

Avståndstransitiva grafer med grader större än tre

Alla distanstransitiva gradgrafer är kända [28] . Alla distanstransitiva grafer av grad (valens) fyra ( ) erhölls av D. Smith 1973-74 [23] [24] , och de femte, sjätte och sjunde graderna 1984 av A. A. Ivanov, A. V. Ivanov och I. A. Faradzhev [ 29] . $k<13$ $k=4$

År 1986 erhöll A. A. Ivanov och A. V. Ivanov alla distanstransitiva grafer av grader från till [30] . $k=8$ $k=13$

Tillvägagångssätt för klassificering

Listor över avståndstransitiva grafer av små grader erhölls inom ramen för ett tillvägagångssätt baserat på att överväga stabilisatorn för en enda vertex och satser som begränsar grafens diameter. A. A. Ivanov kallade detta tillvägagångssätt "lokalt". Det "globala" tillvägagångssättet är baserat på att överväga verkan av automorfismgruppen på uppsättningen av hörn. Detta tillvägagångssätt gör det möjligt att klassificera distanstransitiva grafer på vilka en grupps handling är primitiv. Av dem konstrueras sedan alla andra [22] .

Anteckningar

↑ Godsil och Royle, 2001 , sid. 66.
↑ Biggs, 1971 , sid. 87.
↑ 1 2 Biggs, 1993 , sid. 118.
↑ 1 2 3 Ivanov, Ivanov och Faradzhev, 1984 , sid. 1704.
↑ 12 Cohen , 2004 , sid. 223.
↑ Ivanov, 1994 , sid. 285.
↑ 1 2 Lauri och Scapelatto, 2016 , sid. 33.
↑ 1 2 Biggs, 1993 , sid. 157.
↑ Lauri och Scapelatto, 2016 , sid. 34.
↑ 1 2 3 4 Brouwer, Cohen och Neumaier, 1989 , sid. 136.
↑ Cohen, 2004 , sid. 232.
↑ Godsil och Royle, 2001 , sid. 66-67.
↑ Biggs, 1993 , sid. 158.
↑ Brouwer, Cohen och Neumaier 1989 , sid. 255.
↑ Brouwer, Cohen och Neumaier 1989 , sid. 269.
↑ Van Bon, 2007 , sid. 519.
↑ Brouwer, Cohen och Neumaier 1989 , sid. 261.
↑ Weisstein, Eric W. Livingstone Graph på Wolfram MathWorld- webbplatsen .
↑ Biggs, 1993 , sid. 159.
↑ Adelson-Velsky, Weisfeler, Leman och Faradzhev, 1969 .
↑ 12 Biggs och Smith, 1971 .
↑ 1 2 Ivanov, 1994 , s. 288-292.
↑ 12 Smith , 1973 .
↑ 12 Smith , 1974 .
↑ Cameron PJ, Praeger CE, Saxl J. och Seitz GM On the Sims gissningar och distanstransitiva grafer // Bull. London Math. soc. - 1983. - Vol. 15. - P. 499-506.
↑ Weiss R. Om avståndstransitiva grafer // Bull. London Math. soc. - 1985. - Vol. 17. - S. 253-256.
↑ Brouwer, Cohen och Neumaier 1989 , sid. 214.
↑ Brouwer, Cohen och Neumaier 1989 , sid. 221-225.
↑ Ivanov, Ivanov och Faradzhev, 1984 .
↑ Ivanov och Ivanov, 1988 .

Litteratur

Böcker

Biggs N. Distance-Transitive Graphs // Finite Groups of Automorphisms (eng.) . - London & New York: Cambridge University Press, 1971. - Vol. 6. - s. 86-96. — (London Mathematical Society Lecture Note Series).

Biggs NL Distance-Transitive Graphs // Algebraisk grafteori (engelska) . — 2:a upplagan. - Cambridge University Press, 1993. - S. 155-163. — 205 sid.

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

Cohen AM Distanstransitiva grafer // Ämnen i Algebraisk grafteori / redigerad av LW Beineke, RJ Wilson. - Cambridge University Press, 2004. - Vol. 102. - S. 222-249. - (Encyclopedia of Mathematics and its Applications).

Godsil C., Royle G. Distance-Transitive Graphs // Algebraisk grafteori (engelska) . - New York: Springer-Verlag, 2001. - Vol. 207. - S. 66-69. — (Examinerade texter i matematik). - doi : 10.1007/978-1-4613-0163-9 .
Ivanov AA, Ivanov AV Avståndstransitiva grafer av valens k , 8 < k < 13 // Algebraic, Extremal and Metric Combinatorics 1986 (engelska) / 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 (engelska) // Faradžev IA, Ivanov AA, Klin MH, Woldar AJ (red.) Investigations in Algebraic Theory of Combinatorial Objects. Matematik och dess tillämpningar (Sovjetserien). - Dordrecht: Springer , 1994. - Vol. 84 . - s. 283-378 . - doi : 10.1007/978-94-017-1972-8 .
Lauri J. , Scapelatto R. Ämnen i grafautomorfismer och rekonstruktion . — 2:a upplagan. - Cambridge: Cambridge University Press, 2016. - 188 sid. — (London Mathematical Society Lecture Note Series). - doi : 10.1017/CBO9781316669846 .

Artiklar

Adelson-Velsky G. M., Veisfeler B. Yu., Leman A. A., Faradzhev I. A. Om ett exempel på en graf som inte har en transitiv automorfismgrupp // Reports of the Academy of Sciences . - 1969. - T. 185 , nr 5 . - S. 975-976 .
Ivanov A. A., Ivanov A. V., Faradzhev I. A. Avståndstransitiva grafer av grad 5, 6 och 7 // Zh. Vychisl. matematik. och matta. fysisk _ - 1984. - T. 24 , nr 11 . - S. 1704-1718 .
Biggs NL, Smith DH Om trivalenta grafer // Bulletin of the London Mathematical Society. - 1971. - Vol. 3 , iss. 2 . - S. 155-158 . - doi : 10.1112/blms/3.2.155 .
Smith DH Om tetravalenta grafer // J. Lodon Math. soc. - 1973. - Vol. 6 . - s. 659-662 .
Smith DH Distanstransitiva grafer av valens fyra // J. Lodon Math. soc. - 1974. - Vol. 8 . - s. 377-384 .
Van Bon J. Finita primitiva distanstransitiva grafer (engelska) // European Journal of Combinatorics. - 2007. - Vol. 28 , iss. 2 . - s. 517-532 . - doi : 10.1016/j.ejc.2005.04.014 .

Länkar

Weisstein, Eric W. Distance-Transitive Graph (engelska) på Wolfram MathWorlds webbplats .