Avstånd-regelbunden graf

Distance-regular graph ( engelska distance-regular graph ) - en sådan regelbunden graf , där det för två avståndspunkter och som ligger på samma avstånd från varandra är sant att antalet hörn som faller in på och samtidigt ligger vid ett avstånd från spetsen , beror endast på avståndet mellan spetsarna och ; dessutom beror antalet hörn som faller in på och på ett avstånd från en vertex bara på avståndet . $v$ $w$ $j$ $v$ $j-1$ $w$ $j$ $v$ $w$ $v$ $j+1$ $w$ $j$

Avståndsregelbundna grafer introducerades av N. Biggs 1969 vid en konferens i Oxford [1] , även om själva termen dök upp mycket senare [2] .

Definition

Definition av en avstånd-reguljär graf [3] [4] :

En avstånd-reguljär graf är en oriktad, sammankopplad, avgränsad, regelbunden graf av valens och diameter för vilken följande är sant. Det finns naturliga 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å att för varje par av hörn placerade på avstånd från varandra är det sant: $(u,v)$ $d(u,v)=j$

(1) antalet hörn infallande och på avstånd från är ( )

u

j-1

v

{\displaystyle c_{j))

1\leqslant j\leqslant D

(2) antalet hörn infallande och på avstånd från är ( ).

u

j+1

v

b_{j}

0\leqslant j\leqslant D-1

Sedan

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

är en array av skärningspunkter i grafen (se § Array of intersections ), och är antalet skärningspunkter , där [3] [4] . $\Gamma$ ${\displaystyle a_{j},\,b_{j},\,c_{j))$ ${\displaystyle a_{j}=k-b_{j}-c_{j))$

Array av korsningar

Inledningsvis introducerades termerna "array av korsningar" och "antal korsningar" för att beskriva avståndstransitiva grafer [5] [6] [7] .

Låt det finnas en oriktad, sammankopplad, avgränsad graf, och två av dess hörn är på avstånd från varandra. Alla hörn som träffar vertexen kan delas in i tre uppsättningar , och beroende på deras avstånd till vertexen : $\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\in C\colon d(v,w)=j-1\right\}

Om grafen är avståndstransitiv beror inte uppsättningarnas potenser (kardinaltal) på hörnen utan bara på avståndet . Låt , var är skärningsnumren . $\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 definierar skärningsmatrisen för en avståndstransitiv 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}}

Om är valensen för grafen, då , och . Dessutom är den kompakta formen av skärningsmatrisen: $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}}

Avståndsreguljära och avståndstransitiva grafer

Vid första anblicken är en avståndstransitiv graf och en avståndsreguljär graf mycket nära begrepp. Faktum är att varje avståndstransitiv graf är avståndsregelbunden. Men deras natur är annorlunda. Om en avståndstransitiv graf definieras baserat på grafens symmetri genom automorfismtillståndet, definieras en avståndsreguljär graf utifrån villkoret för dess kombinatoriska regelbundenhet [3] .

En konsekvens av automorfismen hos en distanstransitiv graf är dess regelbundenhet. Följaktligen, för en vanlig graf, kan man bestämma skärningsnumren . Å andra sidan har en distans-reguljär graf en kombinatorisk regelbundenhet, och korsningsnummer definieras också för den (se § Intersection array ), men detta innebär inte en automorfism [8] [9] .

Avståndstransitivitet för en graf antyder dess avståndsregelbundenhet, men det omvända är inte sant [8] . Detta bevisades 1969, till och med före införandet av termen "distanstransitiv graf", av en grupp sovjetiska matematiker ( G.M. Adelson-Velsky , B. Yu. Veisfeler , A.A. Leman, I.A. Faradzhev) [10] [8] . Den minsta avstånds-reguljära grafen som inte är avståndstransitiv är Shrikhande-grafen . Den enda trivalenta grafen av denna typ är Tattas 12-cell , en graf med 126 hörn [8] .

Egenskaper

En avståndsregelbunden graf med diameter 2 är starkt regelbunden , och det omvända är också sant (förutsatt att grafen är kopplad ) [3] .

Egenskaper för en skärningsmatris för en avstånd-reguljär graf

En skärningsmatris av en avstånd-reguljär graf har följande egenskaper [11] [12] :

Varje vertex har ett konstant antal hörn på avstånd från sig , och för alla ; $k_j$ $j$ $k_{0}=1$ $k_{j+1}={\frac {b_{j}k_{j}}{c_{j+1}}}$ $j=0,\,1,\,\dots ,\,D-1$
Ordningen på grafen är ; $n$ ${\displaystyle n=k_{0}+k_{1}+\,\dots \,+k_{D))$
Antalet hörn som är på avstånd från varje hörn uttrycks i termer av antalet skärningar som för alla ; $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$
Produkten av antalet hörn på avstånd från en godtycklig vertex i grafens ordning är ett jämnt värde för alla ; $k_{j}\cdot n$ $j$ $j=1,\,2,\,\dots ,\,D$
Produkten av antalet hörn på avstånd från en godtycklig vertex med antalet skärningar på är ett jämnt värde för alla ; ${\displaystyle k_{j}\cdot a_{j))$ $j$ $a_{j}$ $j=1,\,2,\,\dots ,\,D$
Produkten av antalet skärningar , grafens ordning och dess valens är delbar med 6; $a_{1}\cdot n\cdot k$ $a_{1}$
För korsningsnummer , ; ${\displaystyle c_{j))$ ${\displaystyle 1\leqslant c_{1}\leqslant c_{2}\leqslant \dots \leqslant c_{D))$
För korsningsnummer , ; $b_{j}$ ${\displaystyle k=b_{0}\geqslant b_{1}\geqslant b_{2}\dots \geqslant b_{D-1))$
Om , då ; $i+j\leqslant D$ ${\displaystyle c_{i}\leqslant b_{j))$
Det finns sådant och . $i$ ${\displaystyle k_{0}\leqslant k_{1}\leqslant \dots \leqslant k_{i))$ ${\displaystyle k_{i+1}\geqslant k_{i+2}\geqslant \dots \geqslant k_{D))$

Avståndsmatriser för en transitiv-reguljär graf

Låt en graf vara transitivt regelbunden med diameter , vara antalet av dess hörn och vara grafens valens. Låt oss definiera en uppsättning avståndsmatriser av storlek som [ 3 ] : $\Gamma (V,E)$ $D$ $n=|V|$ $k$ $n\ gånger 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}}

Egenskaper för avståndsmatriser

Avståndsmatriser har följande egenskaper [3] :

${\displaystyle \mathbf {A} _{0}=\mathbf {I} _{n))$ , var är identitetsmatrisen ; $\mathbf {I} _{n}$
$\mathbf {A} _{1}=\mathbf {A}$ är den vanliga grafens närliggande matris ; $\Gamma (V,E)$
$\mathbf {A} _{0}+\mathbf {A} _{1}+\mathbf {A} _{2}+\dots +\mathbf {A} _{D}=\mathbf {J }_{n}$ , var är matrisen av enheter $\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}$ , där är en uppsättning skärningspunkter för en avstånd-reguljär graf och ${\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))$
det finns reella tal sådana att för alla , Och det finns antalet skärningar, det vill säga antalet hörn som är på ett avstånd från vertex och på ett avstånd från vertex , med tanke på avståndet mellan hörnen och . Observera att , , . $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$ $i$ $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))$

Anteckningar

↑ Biggs, 1971 .
↑ Brouwer, Cohen och Neumaier 1989 , sid. 128.
↑ 1 2 3 4 5 6 Biggs, 1993 , sid. 159.
↑ 1 2 Brouwer, Cohen och Neumaier, 1989 , sid. 126.
↑ Biggs, 1971 , sid. arton.
↑ Lauri och Scapelatto, 2016 , sid. 33.
↑ Biggs, 1993 , sid. 157.
↑ 1 2 3 4 Brouwer, Cohen och Neumaier, 1989 , sid. 136.
↑ Cohen, 2004 , sid. 232.
↑ Adelson-Velsky, Weisfeler, Leman och Faradzhev, 1969 .
↑ van Dam, Koolen och Tanaka, 2006 , sid. åtta.
↑ van Dam, Koolen och Tanaka, 2006 , sid. elva.

Litteratur

Adelson-Velsky G. M., Veisfeler B. Yu., Leman A. A., Faradzhev I. A. Om ett exempel på en graf som inte har en transitiv automorfismgrupp // Reports of the Academy of Sciences . - 1969. - T. 185 , nr 5 . - S. 975-976 .
Biggs N. L. Intersection Matrices for Linear Graphs // Combinatorial Mathematics and its applications: procedurer från en konferens som hölls vid Mathematical Institute, Oxford, 7-10 juli 1969 / redigerad av DJA Welsh. - London: Academic press, 1971. - S. 15-23 .
Biggs N. L. Algebraisk grafteori . — 2:a upplagan. - Cambridge University Press , 1993. - 205 sid.
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 // Ämnen i algebraisk grafteori (engelska) / redigerad av 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 (engelska) // The Electronic Journal of Combinatorics : Dynamic surveys. - 2006. - Nej . DS22 .
Lauri J. , Scapelatto R. Ämnen i grafautomorfismer och rekonstruktion . — 2:a upplagan. - Combridge: Combridge University Press, 2016. - 188 sid.