Gráfico de distancia regular

Gráfico de distancia regular ( gráfico de distancia regular en inglés ): un gráfico regular de este tipo , en el que para dos vértices cualesquiera y ubicados a la misma distancia entre sí, es cierto que el número de vértices incidentes y al mismo tiempo ubicados en una distancia al vértice , depende únicamente de la distancia entre los vértices y ; además, el número de vértices incidentes y a una distancia de un vértice también depende solo de la distancia . $v$ $w$ $j$ $v$ $j-1$ $w$ $j$ $v$ $w$ $v$ $j+1$ $w$ $j$

Los gráficos de distancia regular fueron presentados por N. Biggs en 1969 en una conferencia en Oxford [1] , aunque el término en sí apareció mucho más tarde [2] .

Definición

Definición de un gráfico de distancia regular [3] [4] :

Un gráfico de distancia regular es un gráfico regular no dirigido, conectado, acotado y de valencia y diámetro para el cual se cumple lo siguiente. hay numeros naturales ${\ estilo de visualización \ Gamma = (V, E)}$ $k$ $D$

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

tal que para cada par de vértices espaciados a una distancia entre sí , se cumple: $(u,v)$ ${\ estilo de visualización d (u, v) = j}$

(1) el número de vértices incidentes ya una distancia de es ( )

tu

j-1

v

{\ Displaystyle c_ {j}}

{\ estilo de visualización 1 \ leqslant j \ leqslant D}

(2) el número de vértices incidentes ya una distancia de es ( ).

tu

j+1

v

b_{j}

0\leqslant j\leqslant D-1

Después

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

es una matriz de intersecciones del gráfico (ver § Matriz de intersecciones ), y es el número de intersecciones , donde [3] [4] . $\Gama$ ${\displaystyle a_{j},\,b_{j},\,c_{j))$ ${\displaystyle a_{j}=k-b_{j}-c_{j))$

Matriz de intersecciones

Inicialmente, los términos "matriz de intersecciones" y "número de intersecciones" se introdujeron para describir gráficos transitivos de distancia [5] [6] [7] .

Sea un grafo no dirigido, conexo y acotado, y dos de sus vértices estén separados entre sí. Todos los vértices incidentes al vértice se pueden dividir en tres conjuntos , y dependiendo de su distancia al vértice : ${\ estilo de visualización \ Gamma = (V, E)}$ ${\ estilo de visualización u, v \ en V (\ Gamma)}$ ${\ estilo de visualización j = d (u, v)}$ $w$ $tu$ $A$ $B$ $C$ ${\ estilo de visualización d (v, w)}$ $v$

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

Si el gráfico es distancia-transitivo, entonces las potencias (números cardinales) de los conjuntos no dependen de los vértices , sino que dependen únicamente de la distancia . Vamos , ¿dónde están los números de intersección ? $\Gama$ ${\ estilo de visualización | A |, \, | B |, \, | C |}$ $tú, v$ ${\ estilo de visualización j = d (u, v)}$ $a_{j}=|A|,\,b_{j}=|B|,\,c_{j}=|C|$ ${\displaystyle a_{j},\,b_{j},\,c_{j))$

Definimos la matriz de intersección de un gráfico de distancia transitiva como: $\Gama$

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

Si es la valencia de la gráfica, entonces , y . Además, entonces la forma compacta del arreglo de intersección es: $k$ $b_{0}=k$ ${\ estilo de visualización 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 },\,\puntos,\,c_{D}\end{Bmatriz}}

Gráficos distancia-regulares y distancia-transitivos

A primera vista , un gráfico de distancia transitiva y un gráfico de distancia regular son conceptos muy cercanos. De hecho, todo grafo transitivo de distancia es regular en distancia. Sin embargo, su naturaleza es diferente. Si un gráfico de distancia transitiva se define en función de la simetría del gráfico a través de la condición de automorfismo, entonces un gráfico de distancia regular se define a partir de la condición de su regularidad combinatoria [3] .

Una consecuencia del automorfismo de un gráfico transitivo de distancia es su regularidad. En consecuencia, para un gráfico regular, uno puede determinar los números de intersección . Por otro lado, un grafo de distancia regular tiene una regularidad combinatoria, y los números de intersección también se definen para él (ver § Matriz de intersección ), pero esto no implica un automorfismo [8] [9] .

La distancia-transitividad de un gráfico implica su distancia-regularidad, pero lo contrario no es cierto [8] . Esto se demostró en 1969, incluso antes de la introducción del término "gráfico transitivo de distancia", por un grupo de matemáticos soviéticos ( G. M. Adelson-Velsky , B. Yu. Veisfeler , A. A. Leman, I. A. Faradzhev) [10] [8] . El gráfico de distancia regular más pequeño que no es transitivo de distancia es el gráfico de Shrikhande . El único gráfico trivalente de este tipo es el de 12 celdas de Tatta , un gráfico con 126 vértices [8] .

Propiedades

Un gráfico de distancia regular con diámetro 2 es fuertemente regular , y lo contrario también es cierto (siempre que el gráfico esté conectado ) [3] .

Propiedades de una matriz de intersección de un gráfico de distancia regular

Una matriz de intersección de un gráfico de distancia regular tiene las siguientes propiedades [11] [12] :

Cada vértice tiene un número constante de vértices a una distancia de él , y para todos ; $k_j$ $j$ $k_{0}=1$ $k_{j+1}={\frac{b_{j}k_{j}}{c_{j+1}}}$ $j=0,\,1,\,\puntos,\,D-1$
El orden de la gráfica es ; $norte$ ${\displaystyle n=k_{0}+k_{1}+\,\puntos \,+k_{D))$
El número de vértices que están a una distancia de cada vértice se expresa en términos del número de intersecciones para todos ; $j+1$ ${\displaystyle k_{j+1}={\frac {b_{0}b_{1}\puntos b_{j}}{c_{1}c_{2}\puntos c_{j+1))))$ $j=0,\,1,\,\puntos,\,D-1$
El producto del número de vértices a una distancia de un vértice arbitrario por el orden del gráfico es un valor par para todos ; $k_{j}\cdotn$ $j$ $j=1,\,2,\,\puntos,\,D$
El producto del número de vértices a una distancia de un vértice arbitrario por el número de intersecciones es un valor par para todos ; ${\displaystyle k_{j}\cdot a_{j))$ $j$ $a_{j}$ $j=1,\,2,\,\puntos,\,D$
El producto del número de intersecciones , el orden de la gráfica y su valencia es divisible por 6; $a_{1}\cdot n\cdot k$ $un_{1}$
Para números de intersección , ; ${\ Displaystyle c_ {j}}$ ${\displaystyle 1\leqslant c_{1}\leqslant c_{2}\leqslant \dots \leqslant c_{D))$
Para números de intersección , ; $b_{j}$ ${\displaystyle k=b_{0}\geqslant b_{1}\geqslant b_{2}\dots \geqslant b_{D-1))$
Si , entonces ; $i+j\leqslant D$ ${\displaystyle c_{i}\leqslant b_{j))$
Hay tal que y . $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))$

Matrices de distancia de un grafo transitivo-regular

Sea un grafo transitivamente regular de diámetro , sea el número de sus vértices y sea la valencia del grafo. Definamos un conjunto de matrices de distancia de tamaño como [3] : ${\ estilo de visualización \ Gamma (V, E)}$ $D$ ${\ estilo de visualización n=|V|}$ $k$ $n\veces n$ ${\displaystyle \left\{\mathbf {A}_{0},\,\mathbf {A}_{1},\,\dots,\,\mathbf {A}_{D}\right\))$

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

Propiedades de las matrices de distancia

Las matrices de distancia tienen las siguientes propiedades [3] :

${\ estilo de visualización \ mathbf {A} _ {0} = \ mathbf {I} _ {n}}$ , donde es la matriz identidad ; ${\ estilo de visualización \ mathbf {I} _ {n}}$
$\mathbf {A} _{1}=\mathbf {A}$ es la matriz de adyacencia de gráfico habitual ; ${\ estilo de visualización \ Gamma (V, E)}$
$\mathbf {A}_{0}+\mathbf {A}_{1}+\mathbf {A}_{2}+\dots +\mathbf {A}_{D}=\mathbf {J }_{norte}$ , donde es la matriz de unidades ${\ estilo de visualización \ 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}$ , donde es una matriz de intersecciones de un gráfico de distancia regular y ${\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{d-1}\,;\,1,\,c_{2},\,\dots , \,c_{d}\end{Bmatriz}}$ ${\displaystyle a_{i}=k-b_{i}-c_{i))$
existen números reales tales que para todo , y existe el número de intersecciones, es decir, el número de vértices que están a una distancia del vértice ya una distancia del vértice , dada la distancia entre los vértices y . Tenga en cuenta que , , . $p_{i,j}^{h},\ (i,\,j,\,h=0,\,1,\,\puntos,\,D)$ $\mathbf {A}_{i}\mathbf {A}_{j}=\sum_{h=0}^{D}{p_{i,j}^{h}\mathbf {A} _ {h}}$ ${\ estilo de visualización (i, \, j = 0, \, 1, \, \ puntos, \, 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))$

Notas

↑ Biggs, 1971 .
↑ Brouwer, Cohen y Neumaier 1989 , p. 128.
↑ 1 2 3 4 5 6 Biggs, 1993 , pág. 159.
↑ 1 2 Brouwer, Cohen y Neumaier, 1989 , p. 126.
↑ Biggs, 1971 , pág. Dieciocho.
↑ Lauri y Scapelatto, 2016 , pág. 33.
↑ Biggs, 1993 , pág. 157.
↑ 1 2 3 4 Brouwer, Cohen y Neumaier, 1989 , p. 136.
↑ Cohen, 2004 , pág. 232.
↑ Adelson-Velsky, Weisfeler, Leman y Faradzhev, 1969 .
↑ van Dam, Koolen y Tanaka, 2006 , pág. ocho.
↑ van Dam, Koolen y Tanaka, 2006 , pág. once.

Literatura

Adelson-Velsky G. M., Veisfeler B. Yu., Leman A. A., Faradzhev I. A. En un ejemplo de un gráfico que no tiene un grupo de automorfismo transitivo // Informes de la Academia de Ciencias . - 1969. - T. 185 , N º 5 . - S. 975-976 .
Biggs N. L. Matrices de intersección para gráficos lineales // Matemáticas combinatorias y sus aplicaciones: actas de una conferencia celebrada en el Mathematical Institute, Oxford, del 7 al 10 de julio de 1969 / editado por DJA Welsh. - Londres: Prensa académica, 1971. - P. 15-23 .
Biggs N. L. Teoría de grafos algebraicos . — 2ª edición. - Prensa de la Universidad de Cambridge , 1993. - 205 p.
Brouwer A., Cohen A. M., Neumaier A. Distancia de gráficos regulares . - Berlín, Nueva York: Springer Verlag , 1989. - ISBN 3-540-50619-5 , 0-387-50619-5.
Cohen A. M. Gráficos transitivos de distancia // Temas de teoría algebraica de gráficos (inglés) / editado por LW Beineke, RJ Wilson. - Prensa de la Universidad de Cambridge, 2004. - Vol. 102. - Pág. 222-249. - (Enciclopedia de las Matemáticas y sus Aplicaciones).
van Dam E. R., Koolen J. H., Tanaka H. Gráficos de distancia regular (inglés) // The Electronic Journal of Combinatorics: Dynamic Surveys. - 2006. - No. DS22 .
Lauri J. , Scapelatto R. Temas en automorfismos y reconstrucción de grafos . — 2ª edición. - Combridge: Combridge University Press, 2016. - 188 p.