Távolság-szabályos grafikon

Distance-regular graph ( angolul distance-regular graph ) - olyan szabályos gráf , amelyben bármely két , egymástól azonos távolságra lévő csúcsra igaz, hogy a pontba beeső és egyidejűleg elhelyezkedő csúcsok száma távolság a csúcstól , csak a csúcsok és a csúcsok közötti távolságtól függ ; ráadásul a csúcsra eső és attól távol eső csúcsok száma is csak a távolságtól függ . $v$ $w$ $j$ $v$ $j-1$ $w$ $j$ $v$ $w$ $v$ $j+1$ $w$ $j$

A távolságszabályos gráfokat N. Biggs vezette be 1969-ben egy oxfordi konferencián [1] , bár maga a kifejezés sokkal később jelent meg [2] .

Definíció

Távolság-reguláris gráf definíciója [3] [4] :

A távolságszabályos gráf a vegyérték és átmérő irányítatlan, összefüggő, korlátos, szabályos gráfja, amelyre a következő igaz. Vannak természetes számok $\Gamma =(V,E)$ $k$ $D$

b_{0}=k\quad b_{1},\,\dots \,,\,b_{D-1}\ ,\quad c_{1}=1,\quad c_{2},\ ,\pontok ,\,c_{D}

úgy, hogy minden egyes csúcspárra, amelyek egymástól bizonyos távolságra vannak , igaz: $(u,v)$ $d(u,v)=j$

(1 ) a beeső csúcsok száma, amelyek távolsága tőle ( )

u

j-1

v

{\displaystyle c_{j))

1\leqslant j\leqslant D

(2) a beeső és tőle távolságra lévő csúcsok száma ( ) .

u

j+1

v

b_{j}

0\leqslant j\leqslant D-1

Akkor

\iota (\Gamma )={\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{D-1}\,;\,1,\,c_{2 },\,\pontok ,\,c_{D}\end{Bmátrix}}

a gráf metszéspontjainak tömbje ( lásd § Metszéspontok tömbje ), és a metszéspontok száma , ahol [3] [4] . $\Gamma$ ${\displaystyle a_{j},\,b_{j},\,c_{j))$ ${\displaystyle a_{j}=k-b_{j}-c_{j))$

Kereszteződések tömbje

Kezdetben a "metszéspontok tömbje" és a "metszéspontok száma" kifejezéseket vezették be a távolság-tranzitív gráfok leírására [5] [6] [7] .

Legyen egy irányítatlan, összefüggő, korlátos gráf, amelynek két csúcsa távolságra van egymástól. A csúcsra eső összes csúcs három halmazra osztható , és a csúcstól való távolságuktól függően : $\Gamma =(V,E)$ $u,v\in V(\Gamma )$ ${\megjelenítési stílus j=d(u,v)}$ $w$ $u$ $A$ $B$ $C$ $d(v,w)$ $v$

\left\{w\in A\colon d(v,w)=j\right\},\quad \left\{w\in B\colon d(v,w)=j+1\right \},\quad \left\{w\in C\colon d(v,w)=j-1\right\}

Ha a gráf távolságtranzitív, akkor a halmazok hatványai (bíborszámai) nem a csúcsoktól , hanem csak a távolságtól függenek . Legyen , hol vannak a metszéspontok számai . $\Gamma$ $|A|,\,|B|,\,|C|$ $u,v$ ${\megjelenítési stílus j=d(u,v)}$ $a_{j}=|A|,\,b_{j}=|B|,\,c_{j}=|C|$ ${\displaystyle a_{j},\,b_{j},\,c_{j))$

A távolság-tranzitív gráf metszésponti tömbjét a következőképpen definiáljuk : $\Gamma$

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

Ha a gráf vegyértéke, akkor , és . Sőt, akkor a metszéstömb kompakt formája: $k$ $b_{0}=k$ $c_{0}=0$ $c_{1}=1$ $a_{i}+b_{i}+c_{i}=k$

\iota (\Gamma )={\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{D-1}\,;\,1,\,c_{2 },\,\pontok ,\,c_{D}\end{Bmátrix}}

Távolságszabályos és távolság-tranzitív grafikonok

Első pillantásra a távolság-tranzitív gráf és a távolság-reguláris gráf nagyon közeli fogalmak. Valójában minden távolság-tranzitív gráf távolságszabályos. A természetük azonban más. Ha egy távolság-tranzitív gráfot a gráf szimmetriája alapján definiálunk az automorfizmus feltételén keresztül, akkor a távolság-reguláris gráfot a kombinatorikus szabályszerűségének feltételéből határozzuk meg [3] .

A távolság-tranzitív gráf automorfizmusának következménye a szabályossága. Ennek megfelelően egy szabályos gráfhoz meg lehet határozni a metszéspontszámokat . Másrészt a távolságszabályos gráfnak van kombinatorikus szabályossága, és metszéspontszámok is definiálva vannak (lásd § Metszéstömb ), de ez nem jelent automorfizmust [8] [9] .

Egy gráf távolság-tranzitivitása magában foglalja a távolság-szabályszerűségét, de ennek fordítva nem igaz [8] . Ezt 1969-ben, még a „távolság-tranzitív gráf” kifejezés bevezetése előtt bebizonyította a szovjet matematikusok egy csoportja ( G. M. Adelson-Velsky , B. Yu. Veisfeler , A. A. Leman, I. A. Faradzhev) [10] [8]. . A legkisebb távolság-reguláris gráf, amely nem távolságtranzitív, a Shrikhande gráf . Az egyetlen ilyen típusú háromértékű gráf a Tatta-féle 12 cellás gráf, amely 126 csúcsú [8] .

Tulajdonságok

Egy 2-es átmérőjű távolságszabályos gráf erősen szabályos , és fordítva is igaz (feltéve, hogy a gráf össze van kapcsolva ) [3] .

Távolságszabályos gráf metszésponti tömbjének tulajdonságai

Egy távolságszabályos gráf metszésponti tömbje a következő tulajdonságokkal rendelkezik [11] [12] :

Minden csúcsnak állandó számú csúcsa van tőle bizonyos távolságban , és mindegyikhez ; $k_j$ $j$ $k_{0}=1$ $k_{j+1}={\frac {b_{j}k_{j}}{c_{j+1}}}$ $j=0,\,1,\,\dots ,\,D-1$
A gráf sorrendje ; $n$ ${\displaystyle n=k_{0}+k_{1}+\,\pontok \,+k_{D))$
Az egyes csúcsoktól távol eső csúcsok számát a metszéspontok számával fejezzük ki, mint mindennél ; $j+1$ ${\displaystyle k_{j+1}={\frac {b_{0}b_{1}\dots b_{j}}{c_{1}c_{2}\dots c_{j+1))))$ $j=0,\,1,\,\dots ,\,D-1$
Egy tetszőleges csúcstól távol eső csúcsok számának szorzata a gráf sorrendjében páros érték mindenre ; $k_{j}\cdot n$ $j$ $j=1,\,2,\,\pontok ,\,D$
Egy tetszőleges csúcstól távol eső csúcsok számának a metszéspontok számával való szorzata mindenre páros érték ; ${\displaystyle k_{j}\cdot a_{j))$ $j$ $a_{j}$ $j=1,\,2,\,\pontok ,\,D$
A metszéspontok számának , a gráf sorrendjének és vegyértékének szorzata osztható 6-tal; $a_{1}\cdot n\cdot k$ $a_{1}$
A metszéspontszámokhoz , ; ${\displaystyle c_{j))$ ${\displaystyle 1\leqslant c_{1}\leqslant c_{2}\leqslant \dots \leqslant c_{D))$
A metszéspontszámokhoz , ; $b_{j}$ ${\displaystyle k=b_{0}\geqslant b_{1}\geqslant b_{2}\dots \geqslant b_{D-1))$
Ha , akkor ; $i+j\leqslant D$ ${\displaystyle c_{i}\leqslant b_{j))$
Van olyan, hogy és . $én$ ${\displaystyle k_{0}\leqslant k_{1}\leqslant \dots \leqslant k_{i))$ ${\displaystyle k_{i+1}\geqslant k_{i+2}\geqslant \dots \geqslant k_{D))$

Tranzitív-reguláris gráf távolságmátrixai

Legyen egy gráf átmérőjű tranzitív szabályos , legyen csúcsainak száma és a gráf vegyértéke. Határozzuk meg a [3 ] méretű távolságmátrixok halmazát : $\Gamma (V,E)$ $D$ $n=|V|$ $k$ $n\szer n$ ${\displaystyle \left\{\mathbf {A} _{0},\,\mathbf {A} _{1},\,\dots ,\,\mathbf {A} _{D}\jobbra\))$

\left(\mathbf {A} _{h}\right)_{r,s}={\begin{cases}1&:\,d(v_{r},v_{s})=h, \\0&:\,d(v_{r},v_{s})\neq h\end{cases}}

Távolságmátrixok tulajdonságai

A távolságmátrixok a következő tulajdonságokkal rendelkeznek [3] :

${\displaystyle \mathbf {A} _{0}=\mathbf {I} _{n))$ , ahol az azonosságmátrix ; $\mathbf {I} _{n}$
$\mathbf {A} _{1}=\mathbf {A}$ a szokásos gráf szomszédsági mátrix ; $\Gamma (V,E)$
$\mathbf {A} _{0}+\mathbf {A} _{1}+\mathbf {A} _{2}+\pontok +\mathbf {A} _{D}=\mathbf {J }_{n}$ , ahol az egységek mátrixa $\mathbf {J} _{n}$
$\mathbf {A} \mathbf {A} _{i}=b_{i-1}\mathbf {A} _{i-1}+a_{i}\mathbf {A} _{i}+ c_{i+1}\mathbf {A} _{i+1}$ , ahol egy távolságszabályos gráf metszéspontjainak tömbje és ${\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{d-1}\,;\,1,\,c_{2},\,\dots , \,c_{d}\end{Bmátrix}}$ ${\displaystyle a_{i}=k-b_{i}-c_{i))$
vannak valós számok úgy, hogy minden , És van a metszéspontok száma, vagyis azoknak a csúcsoknak a száma, amelyek távolságra vannak a csúcstól és távolságra a csúcstól , tekintettel a csúcsok közötti távolságra és . Vegye figyelembe, hogy , , . $p_{i,j}^{h},\ (i,\,j,\,h=0,\,1,\,\pontok ,\,D)$ $\mathbf {A} _{i}\mathbf {A} _{j}=\sum _{h=0}^{D}{p_{i,j}^{h}\mathbf {A} _{h}}$ ${\megjelenítési stílus (i,\,j=0,\,1,\,\pontok ,\,D)}$ ${\displaystyle p_{i,j}^{h))$ $j$ $v$ $én$ $w$ $h$ $v$ $w$ ${\displaystyle p_{1,i-1}^{i}=c_{i))$ $p_{1,i}^{i}=a_{i}$ $p_{1,i+1}^{i}=b_{i}$

Jegyzetek

↑ Biggs, 1971 .
↑ Brouwer, Cohen és Neumaier 1989 , p. 128.
↑ 1 2 3 4 5 6 Biggs, 1993 , p. 159.
↑ 1 2 Brouwer, Cohen és Neumaier, 1989 , p. 126.
↑ Biggs, 1971 , p. tizennyolc.
↑ Lauri és Scapelatto, 2016 , p. 33.
↑ Biggs, 1993 , p. 157.
↑ 1 2 3 4 Brouwer, Cohen és Neumaier, 1989 , p. 136.
↑ Cohen, 2004 , p. 232.
↑ Adelson-Velsky, Weisfeler, Leman és Faradzhev, 1969 .
↑ van Dam, Koolen és Tanaka, 2006 , p. nyolc.
↑ van Dam, Koolen és Tanaka, 2006 , p. tizenegy.

Irodalom

Adelson-Velsky G. M., Veisfeler B. Yu., Leman A. A., Faradzhev I. A. Egy olyan gráf példáján, amely nem rendelkezik tranzitív automorfizmus csoporttal // A Tudományos Akadémia jelentései . - 1969. - T. 185 , 5. sz . - S. 975-976 .
Biggs N. L. Intersection Matrices for Linear Graphs // Kombinatorikus matematika és alkalmazásai : az oxfordi Mathematical Institute-ban, 1969. július 7-10. között megtartott konferencia előadásai / szerkesztette: DJA Welsh. - London: Academic Press, 1971. - P. 15-23 .
Biggs N. L. Algebrai gráfelmélet . — 2. kiadás. - Cambridge University Press , 1993. - 205 p.
Brouwer A., Cohen A. M., Neumaier A. Távolság szabályos grafikonjai . - Berlin, New York: Springer Verlag , 1989. - ISBN 3-540-50619-5 , 0-387-50619-5.
Cohen A. M. Távolság-tranzitív gráfok // Topics in Algebraic Graph Theory (angol) / szerkesztette: LW Beineke, RJ Wilson. - Cambridge University Press, 2004. - Vol. 102. - P. 222-249. - (Matematika enciklopédiája és alkalmazásai).
van Dam E. R., Koolen J. H., Tanaka H. Distance-regular graphs (angolul) // The Electronic Journal of Combinatorics : Dynamic surveys. - 2006. - Nem. DS22 .
Lauri J. , Scapelatto R. Gráfautomorfizmusok és rekonstrukció témái . — 2. kiadás. - Combridge: Combridge University Press, 2016. - 188 p.