Afstand-regulær graf

Distance-regular graph ( engelsk distance-regular graph ) - sådan en regulær graf , hvor for to vilkårlige spidser og placeret i samme afstand fra hinanden, er det rigtigt, at antallet af spidser, der falder ind på og på samme tid placeret kl. en afstand fra toppunktet , afhænger kun af afstanden mellem toppunkterne og ; desuden afhænger antallet af toppunkter, der falder ind til og i afstand fra et toppunkt , også kun af afstanden . $v$ $w$ $j$ $v$ $j-1$ $w$ $j$ $v$ $w$ $v$ $j+1$ $w$ $j$

Afstandsregulære grafer blev introduceret af N. Biggs i 1969 på en konference i Oxford [1] , selvom selve begrebet dukkede op meget senere [2] .

Definition

Definition af en afstand-regulær graf [3] [4] :

En afstand-regulær graf er en urettet, forbundet, afgrænset, regulær graf af valens og diameter , for hvilken følgende er sandt. Der er naturlige tal $\Gamma =(V,E)$ $k$ $D$

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

sådan, at for hvert par hjørner med afstand fra hinanden er det sandt: $(u,v)$ $d(u,v)=j$

(1) antallet af indfaldende hjørner og i en afstand fra er ( )

u

j-1

v

{\displaystyle c_{j))

1\leqslant j\leqslant D

(2) antallet af hjørner, der falder ind og i en afstand fra er ( ).

u

j+1

v

b_{j}

0\leqslant j\leqslant D-1

Derefter

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

er en matrix af skæringspunkter i grafen (se § Matrix af skæringspunkter ), og er antallet af skæringspunkter , hvor [3] [4] . $\Gamma$ ${\displaystyle a_{j},\,b_{j},\,c_{j))$ ${\displaystyle a_{j}=k-b_{j}-c_{j))$

Array af skæringspunkter

Oprindeligt blev udtrykkene "array af kryds" og "antal kryds" introduceret for at beskrive afstandstransitive grafer [5] [6] [7] .

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$

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

Hvis grafen er afstandstransitiv, afhænger mængdernes potenser (kardinaltal) ikke af hjørnerne , men afhænger kun af afstanden . Lad , hvor er krydsningsnumrene . $\Gamma$ $|A|,\,|B|,\,|C|$ $u, v$ $j=d(u,v)$ $a_{j}=|A|,\,b_{j}=|B|,\,c_{j}=|C|$ ${\displaystyle a_{j},\,b_{j},\,c_{j))$

Vi definerer skæringsarrayet for en afstandstransitiv graf som: $\Gamma$

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

Hvis er grafens valens, så , og . Desuden er den kompakte form af skæringsarrayet: $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 },\,\dots ,\,c_{D}\end{Bmatrix}}

Afstandsregulære og afstandstransitive grafer

Ved første øjekast er en afstand-transitiv graf og en afstand-regulæ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 [3] .

En konsekvens af automorfien af en afstandstransitiv graf er dens regelmæssighed. For en almindelig graf kan man følgelig bestemme skæringsnumrene . På den anden side har en afstand-regulær graf en kombinatorisk regularitet, og skæringsnumre er også defineret for den (se § Intersection array ), men dette indebærer ikke en automorfi [8] [9] .

Afstandstransitivitet af en graf indebærer dens afstandsregularitet, men det modsatte er ikke sandt [8] . 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) [10] [8] . 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 [8] .

Egenskaber

En afstand-regulær graf med diameter 2 er meget regelmæssig , og det omvendte er også sandt (forudsat at grafen er forbundet ) [3] .

Egenskaber for et skæringsarray af en afstand-regulær graf

Et skæringsarray af en afstand-regulær graf har følgende egenskaber [11] [12] :

Hvert toppunkt har et konstant antal hjørner i en afstand fra sig , og for alle ; $k_j$ $j$ $k_{0}=1$ $k_{j+1}={\frac {b_{j}k_{j}}{c_{j+1}}}$ $j=0,\,1,\,\dots ,\,D-1$
Rækkefølgen af grafen er ; $n$ ${\displaystyle n=k_{0}+k_{1}+\,\dots \,+k_{D))$
Antallet af knudepunkter, der er i afstand fra hvert knudepunkt, er udtrykt i antallet af skæringspunkter som for alle ; $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$
Produktet af antallet af toppunkter i en afstand fra et vilkårligt toppunkt efter grafens rækkefølge er en lige værdi for alle ; $k_{j}\cdot n$ $j$ $j=1,\,2,\,\dots ,\,D$
Produktet af antallet af toppunkter i en afstand fra et vilkårligt toppunkt med antallet af skæringspunkter på er en lige værdi for alle ; ${\displaystyle k_{j}\cdot a_{j))$ $j$ $a_{j}$ $j=1,\,2,\,\dots ,\,D$
Produktet af antallet af skæringspunkter , rækkefølgen af grafen og dens valens er deleligt med 6; $a_{1}\cdot n\cdot k$ $a_{1}$
For krydsnumre , ; ${\displaystyle c_{j))$ ${\displaystyle 1\leqslant c_{1}\leqslant c_{2}\leqslant \dots \leqslant c_{D))$
For krydsnumre , ; $b_{j}$ ${\displaystyle k=b_{0}\geqslant b_{1}\geqslant b_{2}\dots \geqslant b_{D-1))$
Hvis , så ; $i+j\leqslant D$ ${\displaystyle c_{i}\leqslant b_{j))$
Der er sådan , at og . $jeg$ ${\displaystyle k_{0}\leqslant k_{1}\leqslant \dots \leqslant k_{i))$ ${\displaystyle k_{i+1}\geqslant k_{i+2}\geqslant \dots \geqslant k_{D))$

Afstandsmatricer for en transitiv-regulær graf

Lad en graf være transitivt regelmæssig af diameter , være antallet af dens hjørner og være grafens valens. Lad os definere et sæt afstandsmatricer af størrelse som [ 3 ] : $\Gamma (V,E)$ $D$ $n=|V|$ $k$ $n\ gange n$ ${\displaystyle \left\{\mathbf {A} _{0},\,\mathbf {A} _{1},\,\dots ,\,\mathbf {A} _{D}\right\))$

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

Egenskaber for afstandsmatricer

Afstandsmatricer har følgende egenskaber [3] :

${\displaystyle \mathbf {A} _{0}=\mathbf {I} _{n))$ , hvor er identitetsmatrixen ; $\mathbf {I} _{n}$
$\mathbf {A} _{1}=\mathbf {A}$ er den sædvanlige graf tilstødende matrix ; $\Gamma (V,E)$
$\mathbf {A} _{0}+\mathbf {A} _{1}+\mathbf {A} _{2}+\dots +\mathbf {A} _{D}=\mathbf {J }_{n}$ , hvor er matrixen af enheder $\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}$ , hvor er en matrix af skæringspunkter for en afstand-regulær graf og ${\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{d-1}\,\,1,\,c_{2},\,\dots, \,c_{d}\end{Bmatrix}}$ ${\displaystyle a_{i}=k-b_{i}-c_{i))$
der er reelle tal sådan, at for alle , Og der er antallet af skæringspunkter, det vil sige antallet af toppunkter, der er i en afstand fra toppunktet og i en afstand fra toppunktet , givet afstanden mellem toppunkterne og . Bemærk at , , . $p_{i,j}^{h},\ (i,\,j,\,h=0,\,1,\,\dots ,\,D)$ $\mathbf {A} _{i}\mathbf {A} _{j}=\sum _{h=0}^{D}{p_{i,j}^{h}\mathbf {A} _{h}}$ $(i,\,j=0,\,1,\,\dots ,\,D)$ ${\displaystyle p_{i,j}^{h))$ $j$ $v$ $jeg$ $w$ $h$ $v$ $w$ ${\displaystyle p_{1,i-1}^{i}=c_{i))$ $p_{1,i}^{i}=a_{i}$ ${\displaystyle p_{1,i+1}^{i}=b_{i))$

Noter

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

Litteratur

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 .
Biggs N. L. Intersection Matrics for Linear Graphs // Kombinatorisk matematik og dens anvendelser: forløb fra en konference afholdt på Mathematical Institute, Oxford, fra 7.-10. juli, 1969 / redigeret af DJA Welsh. - London: Akademisk presse, 1971. - S. 15-23 .
Biggs N. L. Algebraisk grafteori . — 2. udgave. - Cambridge University Press , 1993. - 205 s.
Brouwer A., Cohen A. M., Neumaier A. Distance Regular Graphs . - Berlin, New York: Springer Verlag , 1989. - ISBN 3-540-50619-5 , 0-387-50619-5.
Cohen A. M. Distance-transitive graphs // Emner i Algebraic Graph Theory (engelsk) / redigeret af LW Beineke, RJ Wilson. - Cambridge University Press, 2004. - Vol. 102. - S. 222-249. - (Encyclopedia of Mathematics and its Applications).
van Dam E. R., Koolen J. H., Tanaka H. Distance-regular graphs (engelsk) // The Electronic Journal of Combinatorics : Dynamic surveys. - 2006. - Nej. DS22 .
Lauri J. , Scapelatto R. Emner i grafautomorfismer og rekonstruktion . — 2. udgave. - Combridge: Combridge University Press, 2016. - 188 s.