Etäisyystransitiivinen kaavio

Etäisyystransitiivinen graafi on graafi , jossa mikä tahansa järjestetyt pisteparit muunnetaan joksikin muuksi järjestetyksi pistepariksi, jolla on sama etäisyys pisteiden välillä jollakin graafin automorfismista .

Läheinen käsite on etäisyys-säännöllinen kuvaaja , mutta niiden luonne on erilainen. Jos etäisyystransitiivinen graafi määritellään graafin symmetriasta automorfismiehdon kautta, niin etäisyyssäännöllinen graafi määritellään sen kombinatorisen säännönmukaisuuden ehdosta. Jokainen etäisyystransitiivinen kuvaaja on etäisyyssäännöllinen, mutta päinvastoin ei pidä paikkaansa. Tämä todistettiin vuonna 1969, jo ennen kuin termi "etäisyystransitiivinen graafi" keksittiin.

Etäisyyssäännölliset kaaviot, joiden asteet ovat alle 13, on täysin luokiteltu.

Etäisyystransitiivisen graafin määritelmät

Etäisyystransitiiviselle graafille on olemassa useita muodoltaan erilaisia, mutta merkitykseltään identtisiä määritelmiä. Kuvaajan oletetaan olevan suuntaamaton, yhdistetty ja rajoitettu. Määritelmässä käytetään graafin kärkien välisen etäisyyden ja graafin automorfismin käsitteitä : $\Gamma =(V,E)$

Graafin kahden kärjen välinen etäisyys on reunojen lukumäärä lyhimmän ja yhdistävän polun varrella $d(u,v)$ $u,v\in V(\Gamma )$ $\Gamma =(V,E)$ $u$ $v$
Graafin automorfismi on graafin kärkijoukon yksi-yhteen kartoitus itseensä säilyttäen kärkien vierekkäisyyden. $g:V\rightarrow V$
Kuvaajan automorfismiryhmä on joukko graafin automorfismeja. $\mathrm {Aut} (\Gamma )$

Godzilla-Roylen määritelmä [1] Suuntaamattoman, yhdistetyn, rajoitetun graafin sanotaan olevan etäisyystransitiivinen, jos kahdelle järjestetylle kärkiparille on olemassa sellainen graafin automorfismi , että

\Gamma =(V,E)

(u,v)

(x,y)

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

g

\Gamma

g:(u,v)\nuoli oikealle (x,y)

Bigsin määritelmä [2] [3] Olkoon suuntaamattomalla, yhdistetyllä, rajoitetulla graafilla automorfismiryhmä . Graafin sanotaan olevan etäisyystransitiivinen, jos kaikille pisteille on olemassa automorfismi , joka kuvaa ja

\Gamma =(V,E)

\mathrm {Aut} (\Gamma )

\Gamma

{\näyttötyyli u,v,x,y}

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

g\in G

u\rightarrow x

v\rightarrow y

Määritelmä Ivanov-Ivanov-Faradzhev [4] Suuntaamattoman yhdistetyn äärellisen graafin, jossa ei ole silmukoita ja useita reunoja, sanotaan olevan etäisyystransitiivinen, jos sen automorfismiryhmä toimii transitiivisesti järjestetyissä tasaetäisyyspisteiden pareissa

\Gamma =(V,E)

\mathrm {Aut} (\Gamma )

Cowanin määritelmä [5] Antaa olla yhdistetty halkaisijakaavio ja olla sen automorfismiryhmä. on etäisyys-transitiivinen , jos se on transitiivinen jokaisessa sarjassa , jossa . Graafi on etäisyystransitiivinen, jos sen automorfismiryhmä on siinä etäisyystransitiivinen.

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

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

\Gamma

\mathrm {Aut} (\Gamma )

Määritelmä Ivanovin mukaan [6] Olkoon suuntaamattomalla, yhdistetyllä, rajoitetulla graafilla automorfismiryhmä . Olkoon alaryhmä . Graafia kutsutaan -etäisyys -transitiiviseksi , jos jokaiselle neljälle pisteelle on olemassa automorfismi , joka kuvaa ja . Graafia kutsutaan etäisyystransitiiviseksi, jos se on -etäisyystransitiivinen jollekin graafin automorfismiryhmän alaryhmälle.

\Gamma =(V,E)

\mathrm {Aut} (\Gamma )

G

\mathrm {Aut} (\Gamma )

\Gamma

G

G

{\näyttötyyli u,v,x,y}

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

g\in G

u\rightarrow x

v\rightarrow y

G

G

Toisin sanoen on olemassa -etäisyys-transitiivinen graafi, jos aliryhmä toimii transitiivisesti kunkin joukossa .

\Gamma

G

G

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

i

Joukko risteyksiä

Olkoon suuntaamaton, yhdistetty, rajoitettu graafi, jonka kaksi kärkeä ovat etäisyyden päässä toisistaan. Kaikki kärkeen tulevat kärjet voidaan jakaa kolmeen joukkoon ja riippuen niiden etäisyydestä kärkeen : $\Gamma =(V,E)$ $u,v\in V(\Gamma )$ ${\näyttötyyli j=d(u,v)}$ $w$ $u$ $A$ $B$ $C$ ${\näyttötyyli 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\))

Jos kuvaaja on etäisyystransitiivinen, joukkojen potenssit (kardiaaliluvut) eivät riipu huipuista , vaan riippuvat vain etäisyydestä ja niitä kutsutaan leikkausluvuiksi . $\Gamma$ $a_{j}=|A|,\,b_{j}=|B|,\,c_{j}=|C|$ $u, v$ ${\näyttötyyli j=d(u,v)}$

Joukko risteysnumeroita

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

kutsutaan etäisyystransitiivisen graafin leikkaustaulukoksi [7] [8] .

Ominaisuudet

Jokainen etäisyystransitiivinen graafi on etäisyyssäännöllinen , mutta päinvastoin ei pidä paikkaansa [4] [9] [10] [11] .
Etäisyystransitiivinen graafi on huipputransitiivinen ja symmetrinen [3] .
Joukko etäisyys-säännöllisen asteen kuvaajan leikkauspisteitä $k$ . Koska etäisyystransitiivinen kuvaaja on säännöllinen, leikkausnumerot ja . Lisäksi ,. Siksi etäisyyssäännöllisen graafin leikkaustaulukko voidaan kirjoittaa muodossa [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 },\,\pisteet ,\,c_{d}\end{Bmatrix}}

Esimerkkejä

Yksinkertaisimmat esimerkit etäisyystransitiivisista kaavioista [5] [12] [13] :

täydelliset kaaviot $K_n$
täydelliset kaksiosaiset graafit (biklikit) yhtä suurella osalla $K_{{n,n}}$
hyperkuutiokaavioita $Q_{n}$

Monimutkaisempia esimerkkejä etäisyystransitiivisista kaavioista:

Kreivi Johnson [14]
Grassmann-kaavio [15]
Hammingin määrä [16] [17]
Earl of Livingston [18]

Etäisyyssäännölliset ja etäisyystransitiiviset kuvaajat

Ensi silmäyksellä etäisyystransitiivinen kuvaaja ja etäisyyssäännöllinen graafi ovat hyvin läheisiä käsitteitä. Itse asiassa jokainen etäisyystransitiivinen graafi on etäisyyssäännöllinen. Niiden luonne on kuitenkin erilainen. Jos etäisyystransitiivinen graafi määritellään graafin symmetrian perusteella automorfismiehdon kautta, niin etäisyyssäännöllinen graafi määritellään sen kombinatorisen säännönmukaisuuden ehdosta [19] .

Etäisyystransitiivinen graafi on huipputransitiivinen, ja sille on määritelty leikkausnumerot . Etäisyys-säännöllisen graafin kohdalla leikkausluvut määritellään myös kombinatorisen säännöllisyyden mukaan. Graafin etäisyystransitiivisuus tarkoittaa sen etäisyys-säännöllisyyttä, mutta päinvastoin ei pidä paikkaansa [10] . Tämän todisti vuonna 1969, jo ennen termin "etäisyystransitiivinen graafi" käyttöönottoa, ryhmä neuvostomatemaatikoita ( G. M. Adelson-Velsky , B. Yu. Veisfeler , A. A. Leman, I. A. Faradzhev) [20] [10] . Pienin säännöllinen etäisyyskaavio, joka ei ole etäisyystransitiivinen, on Shrikhande-graafi . Ainoa tämän tyyppinen kolmiarvoinen graafi on Tattan 12-soluinen graafi, jossa on 126 kärkeä [10] .

Etäisyystransitiivisten kuvaajien luokittelu

Ensimmäisen yleisen tuloksen etäisyystransitiivisten kuvaajien luokittelusta saivat Biggs ja Smith [21] vuonna 1971, jolloin kolmannen asteen kuvaajat luokiteltiin. Seuraavien 10-15 vuoden aikana keskeinen ongelma etäisyystransitiivisten kuvaajien tutkimuksessa oli pienten asteiden etäisyystransitiivisten kuvaajien luokittelu [22] . Smith [23] [24] luokitteli täysin etäisyystransitiiviset graafit asteen neljä .

Vuonna 1983 Cameron, Prager, Saxl ja Seitz [25] ja itsenäisesti vuonna 1985 Weiss [26] osoittivat, että jokaiselle kaksi suuremmalle potenssille on rajallinen määrä etäisyystransitiivisia kuvaajia [27] .

Kuutioetäisyystransitiivisten kuvaajien luokitus

Vuonna 1971 N. Biggs ja D. Smith osoittivat lauseen, että kuutioisten (kolmiarvoisten) graafien joukossa on täsmälleen 12 etäisyystransitiivista kuvaajaa [21] :

Laskun nimi	Huippupisteiden lukumäärä	Halkaisija	Ympärysmitta	Risteystaulukko
Täydellinen kaavio K 4	neljä	yksi	3	{3;1}
Täydellinen kaksiosainen graafi K 3,3	6	2	neljä	{3,2;1,3}
Hyperkuutiokaavio $Q_{3}$	kahdeksan	3	neljä	{3,2,1;1,2,3}
Petersenin kreivi	kymmenen	2	5	{3,2;1,1}
Earl of Heawood	neljätoista	3	6	{3,2,2;1,1,3}
Kreivi Pappa	kahdeksantoista	neljä	6	{3,2,2,1;1,1,2,3}
dodekaedrikaavio	kaksikymmentä	5	5	{3,2,1,1,1;1,1,1,2,3}
Kreivi Desargues	kaksikymmentä	5	6	{3,2,2,1,1;1,1,2,2,3}
Earl of Coxeter	28	neljä	7	{3,2,2,1;1,1,1,2}
Thatta-Coxeterin kreivi	kolmekymmentä	neljä	kahdeksan	{3,2,2,2;1,1,1,3}
Earl of Foster	90	kahdeksan	kymmenen	{3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}
Biggs-Smithin jaarli	102	7	9	{3,2,2,2,1,1,1;1,1,1,1,1,1,3}

Etäisyystransitiiviset kuvaajat, joiden aste on suurempi kuin kolme

Kaikki etäisyystransitiiviset astegraafit tunnetaan [28] . Kaikki asteen (valenssin) neljän ( ) etäisyystransitiiviset kuvaajat hankki D. Smith vuosina 1973-74 [23] [24] ja viidennen, kuudennen ja seitsemännen asteen vuonna 1984 A. A. Ivanov, A. V. Ivanov ja I. A. Faradzhev [ 29] . $k<13$ $k = 4$

Vuonna 1986 A. A. Ivanov ja A. V. Ivanov saivat kaikki etäisyystransitiiviset graafit asteista välillä - [30] . $k=8$ $k=13$

Luokittelun lähestymistavat

Listat pienten asteiden etäisyystransitiivisista graafista saatiin sellaisen lähestymistavan puitteissa, joka perustuu yksittäisen kärjen stabilisaattorin ja graafin halkaisijaa rajoittavien lauseiden huomioimiseen. A. A. Ivanov kutsui tätä lähestymistapaa "paikalliseksi". "Globaali" lähestymistapa perustuu automorfismiryhmän toiminnan huomioimiseen kärkijoukossa. Tämä lähestymistapa mahdollistaa etäisyyden transitiivisten kuvaajien luokittelun, joissa ryhmän toiminta on primitiivistä. Niistä rakennetaan sitten kaikki loput [22] .

Muistiinpanot

↑ Godsil ja Royle, 2001 , s. 66.
↑ Biggs, 1971 , s. 87.
↑ 1 2 Biggs, 1993 , s. 118.
↑ 1 2 3 Ivanov, Ivanov ja Farazhev, 1984 , s. 1704.
↑ 12 Cohen , 2004 , s. 223.
↑ Ivanov, 1994 , s. 285.
↑ 1 2 Lauri ja Scapelatto, 2016 , s. 33.
↑ 1 2 Biggs, 1993 , s. 157.
↑ Lauri ja Scapelatto, 2016 , s. 34.
↑ 1 2 3 4 Brouwer, Cohen ja Neumaier, 1989 , s. 136.
↑ Cohen, 2004 , s. 232.
↑ Godsil ja Royle, 2001 , s. 66-67.
↑ Biggs, 1993 , s. 158.
↑ Brouwer, Cohen ja Neumaier 1989 , s. 255.
↑ Brouwer, Cohen ja Neumaier 1989 , s. 269.
↑ Van Bon, 2007 , s. 519.
↑ Brouwer, Cohen ja Neumaier 1989 , s. 261.
↑ Weisstein, Eric W. Livingstone Graph Wolfram MathWorld -verkkosivustolla .
↑ Biggs, 1993 , s. 159.
↑ Adelson-Velsky, Weisfeler, Leman ja Faradzhev, 1969 .
↑ 12 Biggs ja Smith, 1971 .
↑ 1 2 Ivanov, 1994 , s. 288-292.
↑ 12 Smith , 1973 .
↑ 12 Smith , 1974 .
↑ Cameron PJ, Praeger CE, Saxl J. ja Seitz GM On the Sims -oletus ja etäisyystransitiiviset kaaviot // Bull. Lontoon matematiikka. soc. - 1983. - Voi. 15. - s. 499-506.
↑ Weiss R. Etäisyystransitiivisista kaavioista // Bull. Lontoon matematiikka. soc. - 1985. - Voi. 17. - s. 253-256.
↑ Brouwer, Cohen ja Neumaier 1989 , s. 214.
↑ Brouwer, Cohen ja Neumaier 1989 , s. 221-225.
↑ Ivanov, Ivanov ja Farazhev, 1984 .
↑ Ivanov ja Ivanov, 1988 .

Kirjallisuus

Kirjat

Biggs N. Distance-Transitive Graphs // Automorfismien rajalliset ryhmät (eng.) . - London & New York: Cambridge University Press, 1971. - Voi. 6. - s. 86-96. — (London Mathematical Society Lecture Note Series).

Biggs NL Distance-Transitive Graphs // Algebraic Graph Theory (englanti) . – 2. painos. - Cambridge University Press, 1993. - S. 155-163. - 205 p.

Brouwer AE, Cohen AM, Neumaier A. Etäisyys - Transsitiiviset kaaviot // Etäisyys-säännölliset kaaviot . - New York: Springer-Verlag, 1989. - P. 214-234.

Cohen AM Distance-transitive graphs // Toics in Algebraic Graph Theory / toimittanut LW Beineke, RJ Wilson. - Cambridge University Press, 2004. - Voi. 102. - s. 222-249. - (Matematiikan tietosanakirja ja sen sovellukset).

Godsil C., Royle G. Distance-Transitive Graphs // Algebraic Graph Theory (englanti) . - New York: Springer-Verlag, 2001. - Voi. 207. - s. 66-69. — (Matematiikan tutkinnon tekstit). - 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 (englanti) / Deza, M., Frankl, P., & Rosenberg, I. (Toim.) . - Cambridge: Cambridge University Press, 1988. - P. 112-145. — (London Mathematical Society Lecture Note Series). - doi : 10.1017/CBO9780511758881 .

Ivanov AA Distance-Transitive Graphs and Their Classification (englanniksi) // Faradžev IA, Ivanov AA, Klin MH, Woldar AJ (toim.) Investigations in Algebraic Theory of Combinatorial Objects. Matematiikka ja sen sovellukset (Neuvostoliiton sarja). - Dordrecht: Springer , 1994. - Voi. 84 . - s. 283-378 . - doi : 10.1007/978-94-017-1972-8 .
Lauri J. , Scapelatto R. Graph Automorphisms and Reconstruction -aiheet . – 2. painos. - Cambridge: Cambridge University Press, 2016. - 188 s. — (London Mathematical Society Lecture Note Series). - doi : 10.1017/CBO9781316669846 .

Artikkelit

Adelson-Velsky G. M., Veisfeler B. Yu., Leman A. A., Faradzhev I. A. Esimerkki kaaviosta, jossa ei ole transitiivista automorfismiryhmää // Tiedeakatemian raportit . - 1969. - T. 185 , nro 5 . - S. 975-976 .
Ivanov A. A., Ivanov A. V., Faradzhev I. A. Etäisyystransitiiviset graafit asteikoilla 5, 6 ja 7 // Zh. Vychisl. matematiikka. ja matto. fyysinen_ _ - 1984. - T. 24 , nro 11 . - S. 1704-1718 .
Biggs NL, Smith DH Trivalenttisista kaavioista // Bulletin of the London Mathematical Society. - 1971. - Voi. 3 , iss. 2 . - s. 155-158 . - doi : 10.1112/blms/3.2.155 .
Smith DH Neliarvoisilla kaavioilla // J. Lodon Math. soc. - 1973. - Voi. 6 . - s. 659-662 .
Smith DH Valenssin neljä etäisyystransitiiviset graafit // J. Lodon Math. soc. - 1974. - Voi. 8 . - s. 377-384 .
Van Bon J. Finite primitive distance-transitive graphs (Englanti) // European Journal of Combinatorics. - 2007. - Voi. 28 , iss. 2 . - s. 517-532 . - doi : 10.1016/j.ejc.2005.04.014 .

Linkit

Weisstein, Eric W. Distance-Transitive Graph (englanniksi) Wolfram MathWorld -verkkosivustolla .