Afstandstransitiv graf

En afstandstransiv graf er en graf , hvor et hvilket som helst ordnet par af hjørner er oversat til et hvilket som helst andet ordnet par af knudepunkter med samme afstand mellem spidser af en af grafens automorfismer .

Et tæt begreb er en afstand-regulær graf , men deres natur er anderledes. Hvis en afstandstransitiv graf er defineret ud fra grafens symmetri gennem automorfitilstanden, defineres en afstandsregulær graf ud fra betingelsen om dens kombinatoriske regularitet. Hver afstandstransitiv graf er afstandsregulær, men det modsatte er ikke sandt. Dette blev bevist i 1969, selv før udtrykket "distance-transitive graph" blev opfundet.

Afstandsregulære grafer med grader mindre end 13 er fuldstændigt klassificerede.

Definitioner af en afstandstransitiv graf

Der er flere forskellige i form, men identiske i betydning, definitioner af en afstand-transitiv graf. Grafen antages at være urettet, forbundet og afgrænset. Definitionen bruger begreberne afstand mellem grafens toppunkter og grafautomorfi : $\Gamma =(V,E)$

Afstanden mellem to hjørner af en graf er antallet af kanter langs den korteste vej, der forbinder og $d(u,v)$ $u,v\in V(\Gamma )$ $\Gamma =(V,E)$ $u$ $v$
En grafautomorfi er en en-til-en-kortlægning af sættet af hjørner af en graf på sig selv, hvilket bevarer tilstødende hjørner. $g:V\rightarrow V$
En grafautomorfigruppe er et sæt grafautomorfismer. $\mathrm {Aut} (\Gamma )$

Godzilla-Royle definition [1] En urettet, forbundet, afgrænset graf siges at være afstandstransitiv, hvis den for et hvilket som helst to ordnede par af dens hjørner og sådan, at der eksisterer en grafautomorfi , således at

\Gamma =(V,E)

(u,v)

(x,y)

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

g

\Gamma

g:(u,v)\højrepil (x,y)

Biggs definition [2] [3] Lad en urettet, forbundet, afgrænset graf have en automorfigruppe . En graf siges at være afstandstransitiv, hvis der for alle toppunkter eksisterer en automorfi , som kortlægger og

\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 ifølge Ivanov-Ivanov-Faradzhev [4] En urettet forbundet finit graf uden sløjfer og flere kanter siges at være afstandstransitiv, hvis dens automorfigruppe virker transitivt på ordnede par af ækvidistante hjørner

\Gamma =(V,E)

\mathrm {Aut} (\Gamma )

Definition ifølge Cowan [5] Lad være en forbundet diameter graf og være dens automorfi gruppe. er afstandstransitiv tændt, hvis den er transitiv på hvert sæt , hvor . En graf er afstandstransitiv, hvis dens automorfigruppe er afstandstransitiv på den.

\Gamma =(V,E)

D

\mathrm {Aut} (\Gamma )

\mathrm {Aut} (\Gamma )

\Gamma

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

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

\Gamma

\mathrm {Aut} (\Gamma )

Definition ifølge Ivanov [6] Lad en urettet, forbundet, afgrænset graf have en automorfigruppe . Lad der være en undergruppe . En graf kaldes -afstand -transitiv, hvis der for hver fire hjørner er en automorfi , der kortlægger og . En graf kaldes afstandstransitiv, hvis den er -afstandstransitiv for en eller anden undergruppe af grafens automorfigruppe.

\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 andre ord er der en -distance-transitiv graf, hvis undergruppen virker transitivt på sættet for hver .

\Gamma

G

G

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

jeg

Array af skæringspunkter

Lad der være en urettet, forbundet, afgrænset graf, og to af dens hjørner er i afstand fra hinanden. Alle toppunkter , der falder ind på toppunktet , kan opdeles i tre sæt og afhængigt af deres afstand til toppunktet : $\Gamma =(V,E)$ $u,v\in V(\Gamma )$ $j=d(u,v)$ $w$ $u$ $EN$ $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\))

Hvis grafen er afstandstransitiv, så afhænger mængdernes potenser (kardinaltal) ikke af toppunkterne , men afhænger kun af afstanden og kaldes skæringsnumre . $\Gamma$ $a_{j}=|A|,\,b_{j}=|B|,\,c_{j}=|C|$ $u, v$ $j=d(u,v)$

Sæt af krydsnumre

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

kaldes skæringsarrayet for en afstandstransitiv graf [7] [8] .

Egenskaber

Hver afstandstransitiv graf er afstandsregulær , men det modsatte er ikke sandt [4] [9] [10] [11] .
En afstandstransitiv graf er toppunkttransitiv og symmetrisk [3] .
En matrix af skæringspunkter for en afstand-regulær graf af grad $k$ . Da den afstand-transitive graf er regulær, skæringsnumrene og . Desuden . Derfor kan skæringsarrayet for en afstand-regulær graf skrives 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}}

Eksempler

De enkleste eksempler på afstandstransitive grafer [5] [12] [13] :

komplette grafer $K_n$
komplette todelte grafer (bicliques) med lige dele $K_{{n,n}}$
hyperkubegrafer $Q_{n}$

Mere komplekse eksempler på afstandstransitive grafer:

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

Afstandsregulære og afstandstransitive grafer

Ved første øjekast er en afstandstransitiv graf og en afstandsregulær graf meget tætte begreber. Faktisk er enhver afstandstransitiv graf afstandsregulær. Men deres natur er anderledes. Hvis en afstandstransitiv graf er defineret baseret på grafens symmetri gennem automorfi-tilstanden, så defineres en afstand-regulær graf ud fra betingelsen om dens kombinatoriske regularitet [19] .

En afstandstransitiv graf er toppunkttransitiv, og skæringsnumre er defineret for den . For en afstand-regulær graf er skæringsnumrene også defineret i form af kombinatorisk regularitet. Afstandstransitivitet af en graf indebærer dens afstandsregularitet, men det modsatte er ikke sandt [10] . Dette blev bevist i 1969, selv før introduktionen af udtrykket "distance-transitive graph", af en gruppe sovjetiske matematikere ( G. M. Adelson-Velsky , B. Yu. Veisfeler , A. A. Leman, I. A. Faradzhev) [20] [10] . Den mindste afstand-regulære graf, der ikke er afstandstransitiv, er Shrikhande-grafen . Den eneste trivalente graf af denne type er Tattas 12-celle , en graf med 126 hjørner [10] .

Klassifikation af afstandstransitive grafer

Det første generelle resultat i klassificeringen af afstandstransitive grafer blev opnået af Biggs og Smith [21] i 1971, hvor grafer af grad tre blev klassificeret. I løbet af de næste ti til femten år var det centrale problem i studiet af afstandstransitive grafer klassificeringen af afstandstransitive grafer af små grader [22] . Afstandstransitive grafer af grad fire blev fuldstændigt klassificeret af Smith [23] [24] .

I 1983 Cameron, Prager, Saxl og Seitz [25] og uafhængigt i 1985 Weiss [26] beviste, at for enhver magt større end to er der et begrænset antal afstandstransitive grafer [27] .

Klassifikation af kubiske afstand-transitive grafer

I 1971 beviste N. Biggs og D. Smith sætningen om, at der blandt kubiske (trivalente) grafer er nøjagtig 12 afstandstransitive grafer [21] :

Tælle navn	Antal hjørner	Diameter	Omkreds	Skæringsarray
Komplet graf K 4	fire	en	3	{3;1}
Komplet todelt graf K 3,3	6	2	fire	{3,2;1,3}
Hypercube graf $Q_{3}$	otte	3	fire	{3,2,1;1,2,3}
Greve af Petersen	ti	2	5	{3,2;1,1}
jarl af Heawood	fjorten	3	6	{3,2,2;1,1,3}
Greve Pappa	atten	fire	6	{3,2,2,1;1,1,2,3}
dodekaeder graf	tyve	5	5	{3,2,1,1,1;1,1,1,2,3}
Grev Desargues	tyve	5	6	{3,2,2,1,1;1,1,2,2,3}
Jarl af Coxeter	28	fire	7	{3,2,2,1;1,1,1,2}
Greve af Thatta-Coxeter	tredive	fire	otte	{3,2,2,2;1,1,1,3}
Jarl af Foster	90	otte	ti	{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}
Jarl af Biggs-Smith	102	7	9	{3,2,2,2,1,1,1;1,1,1,1,1,1,3}

Afstandstransitive grafer med grader større end tre

Alle afstandstransitive gradgrafer er kendte [28] . Alle afstandstransitive grafer af grad (valens) fire ( ) blev opnået af D. Smith i 1973-74 [23] [24] , og den femte, sjette og syvende grad i 1984 af A. A. Ivanov, A. V. Ivanov og I. A. Faradzhev [ 29] . $k<13$ $k=4$

I 1986 opnåede A. A. Ivanov og A. V. Ivanov alle afstandstransitive grafer af grader fra til [30] . $k=8$ $k=13$

Tilgange til klassificering

Lister over afstandstransitive grafer af små grader blev opnået inden for rammerne af en tilgang baseret på at overveje stabilisatoren af et enkelt toppunkt og teoremer, der begrænser grafens diameter. A. A. Ivanov kaldte denne tilgang "lokal". Den "globale" tilgang er baseret på at overveje virkningen af automorfigruppen på sættet af toppunkter. Denne tilgang gør det muligt at klassificere afstandstransitive grafer, hvorpå en gruppes handling er primitiv. Ud fra dem, så er alle de øvrige konstrueret [22] .

Noter

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

Litteratur

Bøger

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 (engelsk) . — 2. udgave. - Cambridge University Press, 1993. - S. 155-163. — 205 sider.

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

Cohen AM Afstandstransitive grafer // Emner i algebraisk grafteori / redigeret af 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 (engelsk) . - New York: Springer-Verlag, 2001. - Vol. 207. - S. 66-69. — (Kandidattekster i Matematik). - doi : 10.1007/978-1-4613-0163-9 .
Ivanov AA, Ivanov AV Afstandstransitive grafer af valens k , 8 < k < 13 // Algebraic, Extremal and Metric Combinatorics 1986 (engelsk) / 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 (engelsk) // Faradžev IA, Ivanov AA, Klin MH, Woldar AJ (eds.) Investigations in Algebraic Theory of Combinatorial Objects. Matematik og dens anvendelser (sovjetiske serier). - Dordrecht: Springer , 1994. - Vol. 84 . - S. 283-378 . - doi : 10.1007/978-94-017-1972-8 .
Lauri J. , Scapelatto R. Emner i grafautomorfismer og rekonstruktion . — 2. udgave. - Cambridge: Cambridge University Press, 2016. - 188 s. — (London Mathematical Society Lecture Note Series). - doi : 10.1017/CBO9781316669846 .

Artikler

Adelson-Velsky G. M., Veisfeler B. Yu., Leman A. A., Faradzhev I. A. Om et eksempel på en graf, der ikke har en transitiv automorfismegruppe // Rapporter fra Videnskabernes Akademi . - 1969. - T. 185 , nr. 5 . - S. 975-976 .
Ivanov A. A., Ivanov A. V., Faradzhev I. A. Afstandstransitive grafer af grad 5, 6 og 7 // Zh. Vychisl. matematik. og mat. fysisk _ - 1984. - T. 24 , nr. 11 . - S. 1704-1718 .
Biggs NL, Smith DH Om trivalente grafer // Bulletin of the London Mathematical Society. - 1971. - Bd. 3 , iss. 2 . - S. 155-158 . - doi : 10.1112/blms/3.2.155 .
Smith DH Om tetravalente grafer // J. Lodon Math. soc. - 1973. - Bd. 6 . - s. 659-662 .
Smith DH Afstandstransitive grafer af valens fire // J. Lodon Math. soc. - 1974. - Bd. 8 . - s. 377-384 .
Van Bon J. Finite primitive distance-transitive graphs (engelsk) // European Journal of Combinatorics. - 2007. - Bd. 28 , udg. 2 . - s. 517-532 . - doi : 10.1016/j.ejc.2005.04.014 .