Graficul distanță-regular

Graficul distant-regular ( engleză distance-regular graph ) - un astfel de grafic regulat , în care pentru oricare două vârfuri și situate la aceeași distanță unul de celălalt, este adevărat că numărul de vârfuri incidente și în același timp situate la o distanta de la varf , depinde numai de distanta dintre varfuri si ; în plus, numărul de vârfuri incidente la și la o distanță de un vârf depinde, de asemenea, doar de distanța . $v$ $w$ $j$ $v$ $j-1$ $w$ $j$ $v$ $w$ $v$ $j+1$ $w$ $j$

Graficele distanței regulate au fost introduse de N. Biggs în 1969 la o conferință la Oxford [1] , deși termenul în sine a apărut mult mai târziu [2] .

Definiție

Definiția unui grafic distanță-regular [3] [4] :

Un grafic distanță-regular este un grafic nedirecționat, conexat, mărginit, regulat de valență și diametru pentru care următoarele sunt adevărate. Există numere naturale $\Gamma =(V,E)$ $k$ $D$

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

astfel încât pentru fiecare pereche de vârfuri distanțate la o distanță unul de celălalt , este adevărat: $(u,v)$ $d(u,v)=j$

(1) numărul de vârfuri incidente și la o distanță de este ( )

u

j-1

v

c_{j)

1\leqslant j\leqslant D

(2) numărul de vârfuri incidente și la o distanță de este ( ).

u

j+1

v

B j}

0\leqslant j\leqslant D-1

Apoi

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

este o matrice de intersecții ale graficului (vezi § Matrice de intersecții ), și este numărul de intersecții , unde [3] [4] . $\Gamma$ $a_{j},\,b_{j},\,c_{j)$ $a_{j}=k-b_{j}-c_{j)$

Matrice de intersecții

Inițial, termenii „matrice de intersecții” și „număr de intersecții” au fost introduși pentru a descrie graficele tranzitive la distanță [5] [6] [7] .

Să existe un graf nedirecționat, conexat, mărginit, iar două dintre vârfurile sale sunt la o distanță unul de celălalt. Toate vârfurile incidente la vârf pot fi împărțite în trei seturi și în funcție de distanța lor până la vârf : $\Gamma =(V,E)$ $u,v\in V(\Gamma )$ $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\în C\colon d(v,w)=j-1\right\}

Dacă graficul este tranzitiv la distanță, atunci puterile (numerele cardinale) ale mulțimilor nu depind de vârfuri , ci depind doar de distanță . Fie , unde sunt numerele de intersecție . $\Gamma$ $|A|,\,|B|,\,|C|$ $u,v$ $j=d(u,v)$ $a_{j}=|A|,\,b_{j}=|B|,\,c_{j}=|C|$ $a_{j},\,b_{j},\,c_{j)$

Definim matricea de intersectie a unui grafic distant-tranzitiv ca: $\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}}

Dacă este valența graficului, atunci , și . Mai mult, , atunci forma compactă a tabloului de intersecție este: $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}}

Grafice distanță-regulată și distanță-tranzitivă

La prima vedere , un grafic distanță-tranzitiv și un grafic distanță-regular sunt concepte foarte apropiate. Într-adevăr, fiecare grafic tranzitiv la distanță este regulat la distanță. Cu toate acestea, natura lor este diferită. Dacă un graf distanță-tranzitiv este definit pe baza simetriei grafului prin condiția de automorfism, atunci un graf distanță-regular este definit din condiția regularității sale combinatorii [3] .

O consecință a automorfismului unui graf distanță-tranzitiv este regularitatea acestuia. În consecință, pentru un grafic obișnuit, se pot determina numerele de intersecție . Pe de altă parte, un graf distanță-regular are o regularitate combinatorie, iar numerele de intersecție sunt, de asemenea, definite pentru el (vezi § Intersection array ), dar acest lucru nu implică un automorfism [8] [9] .

Distanța-tranzitivitatea unui grafic implică distanța-regularitatea acestuia, dar inversul nu este adevărat [8] . Acest lucru a fost dovedit în 1969, chiar înainte de introducerea termenului de „graf tranzitiv distanță”, de către un grup de matematicieni sovietici ( G. M. Adelson-Velsky , B. Yu. Veisfeler , A. A. Leman, I. A. Faradzhev ) [10] [8] . Cel mai mic grafic distanță-regular care nu este tranzitiv la distanță este graficul Shrikhande . Singurul grafic trivalent de acest tip este cel cu 12 celule al lui Tatta , un grafic cu 126 de vârfuri [8] .

Proprietăți

Un grafic distanță-regular cu diametrul 2 este puternic regulat , iar inversul este de asemenea adevărat (cu condiția ca graficul să fie conectat ) [3] .

Proprietăți ale unui tablou de intersecție a unui grafic distanță-regular

O matrice de intersecție a unui grafic distanță-regular are următoarele proprietăți [11] [12] :

Fiecare vârf are un număr constant de vârfuri la distanță de el și pentru toate ; $k_j$ $j$ $k_{0}=1$ $k_{j+1}={\frac {b_{j}k_{j}}{c_{j+1}}}$ $j=0,\,1,\,\dots ,\,D-1$
Ordinea graficului este ; $n$ $n=k_{0}+k_{1}+\,\dots \,+k_{D)$
Numărul de vârfuri care se află la distanță de fiecare vârf este exprimat în termeni de număr de intersecții ca pentru toate ; $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$
Produsul numărului de vârfuri aflate la distanță de un vârf arbitrar de ordinea graficului este o valoare pară pentru toate ; $k_{j}\cdot n$ $j$ $j=1,\,2,\,\dots ,\,D$
Produsul numărului de vârfuri aflate la o distanță de un vârf arbitrar cu numărul de intersecții pe este o valoare pară pentru toate ; $k_{j}\cdot a_{j)$ $j$ $a_{j}$ $j=1,\,2,\,\dots ,\,D$
Produsul dintre numărul de intersecții , ordinea graficului și valența acestuia este divizibil cu 6; $a_{1}\cdot n\cdot k$ $a_{1}$
Pentru numerele de intersecție , ; $c_{j)$ $1\leqslant c_{1}\leqslant c_{2}\leqslant \dots \leqslant c_{D)$
Pentru numerele de intersecție , ; $B j}$ $k=b_{0}\geqslant b_{1}\geqslant b_{2}\dots \geqslant b_{D-1)$
Dacă , atunci ; $i+j\leqslant D$ $c_{i}\leqslant b_{j)$
Există așa că și . $i$ $k_{0}\leqslant k_{1}\leqslant \dots \leqslant k_{i)$ $k_{i+1}\geqslant k_{i+2}\geqslant \dots \geqslant k_{D)$

Matrici de distanțe ale unui graf tranzitiv-regular

Fie un grafic să fie tranzitiv regulat de diametru , să fie numărul vârfurilor sale și să fie valența graficului. Să definim un set de matrici de distanțe de dimensiune ca [3] : $\Gamma (V,E)$ $D$ $n=|V|$ $k$ $n\ ori 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}}

Proprietăți ale matricelor de distanță

Matricele de distanțe au următoarele proprietăți [3] :

$\mathbf {A} _{0}=\mathbf {I} _{n)$ , unde este matricea de identitate ; $\mathbf {I} _{n}$
$\mathbf {A} _{1}=\mathbf {A}$ este matricea obișnuită de adiacență a graficului ; $\Gamma (V,E)$
$\mathbf {A} _{0}+\mathbf {A} _{1}+\mathbf {A} _{2}+\dots +\mathbf {A} _{D}=\mathbf {J }_{n}$ , unde este matricea unităților $\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}$ , unde este o matrice de intersecții ale unui grafic distanță-regular și ${\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{d-1}\,;\,1,\,c_{2},\,\dots , \,c_{d}\end{Bmatrix}}$ $a_{i}=k-b_{i}-c_{i)$
există numere reale astfel încât pentru toate , și există numărul de intersecții, adică numărul de vârfuri care se află la distanță de vârf și la distanță de vârf , dată fiind distanța dintre vârfuri și . Rețineți că , , . $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)$ $p_{i,j}^{h)$ $j$ $v$ $i$ $w$ $h$ $v$ $w$ $p_{1,i-1}^{i}=c_{i)$ $p_{1,i}^{i}=a_{i}$ $p_{1,i+1}^{i}=b_{i)$

Note

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

Literatură

Adelson-Velsky G. M., Veisfeler B. Yu., Leman A. A., Faradzhev I. A. Pe un exemplu de grafic care nu are un grup de automorfism tranzitiv // Rapoarte ale Academiei de Științe . - 1969. - T. 185 , nr 5 . - S. 975-976 .
Biggs N. L. Intersection Matrices for Linear Graphs // Matematica combinatorică și aplicațiile sale : lucrările unei conferințe ținute la Institutul de Matematică, Oxford, în perioada 7-10 iulie 1969 / editată de DJA Welsh. - Londra: Academic Press, 1971. - P. 15-23 .
Biggs N. L. Teoria graficelor algebrice . — ediția a II-a. - Cambridge University Press , 1993. - 205 p.
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. Grafice tranzitive la distanță // Subiecte în teoria graficelor algebrice (engleză) / editată de LW Beineke, RJ Wilson. - Cambridge University Press, 2004. - Vol. 102. - P. 222-249. - (Enciclopedia Matematicii si aplicatiile sale).
van Dam E. R., Koolen J. H., Tanaka H. Distance-regular graphs (engleză) // The Electronic Journal of Combinatorics : Dynamic surveys. - 2006. - Nr. DS22 .
Lauri J. , Scapelatto R. Topics in Graph Automorphisms and Reconstruction . — ediția a II-a. - Combridge: Combridge University Press, 2016. - 188 p.