Gráfico de distancia regular

Propiedad gráfica

En el campo matemático de la teoría de grafos , una gráfica de distancia regular es una gráfica regular tal que para dos vértices cualesquiera v y w , el número de vértices a la distancia j de v y a la distancia k de w depende sólo de j , k y la distancia entre v y w .

Algunos autores excluyen de esta definición los gráficos completos y los gráficos desconectados.

Todo gráfico transitivo de distancia es regular en distancia. De hecho, los gráficos de distancia regular se introdujeron como una generalización combinatoria de los gráficos de distancia transitiva, teniendo las propiedades de regularidad numérica de estos últimos sin necesariamente tener un gran grupo de automorfismos .

matrices de intersección

La matriz de intersección de un gráfico de distancia regular es la matriz en la que está el diámetro del gráfico y para cada uno , da el número de vecinos de a distancia de y da el número de vecinos de a distancia de para cualquier par de vértices y en distancia . También está el número que da el número de vecinos a distancia de . Los números se llaman números de intersección del gráfico. Satisfacen la ecuación donde está la valencia , es decir, el número de vecinos, de cualquier vértice. ${\displaystyle (b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d})}$ ${\displaystyle d}$ ${\displaystyle 1\leq j\leq d}$ ${\displaystyle b_{j}}$ ${\displaystyle u}$ ${\displaystyle j+1}$ ${\displaystyle v}$ ${\displaystyle c_{j}}$ ${\displaystyle u}$ ${\displaystyle j-1}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle j}$ ${\displaystyle a_{j}}$ ${\displaystyle u}$ ${\displaystyle j}$ ${\displaystyle v}$ ${\displaystyle a_{j},b_{j},c_{j}}$ ${\displaystyle a_{j}+b_{j}+c_{j}=k,}$ ${\displaystyle k=b_{0}}$

Resulta que una gráfica de diámetro es regular en distancias si y sólo si tiene una matriz de intersección en el sentido anterior. ${\displaystyle G}$ ${\displaystyle d}$

Gráficos coespectrales y desconectados de distancia regular.

Un par de gráficos conectados de distancia regular son coespectrales si sus matrices de adyacencia tienen el mismo espectro . Esto equivale a que tengan la misma matriz de intersecciones.

Un gráfico de distancia regular está desconectado si y solo si es una unión disjunta de gráficos coespectrales de distancia regular.

Propiedades

Supongamos que es un gráfico de valencia regular de distancia conectado con una matriz de intersección . Para cada uno, denotamos el número de vértices a distancia de cualquier vértice dado y denotamos el gráfico regular con matriz de adyacencia formada al relacionar pares de vértices a distancia . ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle (b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d})}$ ${\displaystyle 0\leq j\leq d,}$ ${\displaystyle k_{j}}$ ${\displaystyle k}$ ${\displaystyle G_{j}}$ ${\displaystyle k_{j}}$ ${\displaystyle A_{j}}$ ${\displaystyle G}$ ${\displaystyle j}$

Propiedades de la teoría de grafos

• ${\displaystyle {\frac {k_{j+1}}{k_{j}}}={\frac {b_{j}}{c_{j+1}}}}$para todos . ${\displaystyle 0\leq j<d}$
• ${\displaystyle b_{0}>b_{1}\geq \cdots \geq b_{d-1}>0}$y . ${\displaystyle 1=c_{1}\leq \cdots \leq c_{d}\leq b_{0}}$

Propiedades espectrales

• ${\displaystyle G}$tiene valores propios distintos. ${\displaystyle d+1}$
• El único valor propio simple de is o ambos y if es bipartito. ${\displaystyle G}$ ${\displaystyle k,}$ ${\displaystyle k}$ ${\displaystyle -k}$ ${\displaystyle G}$
• ${\displaystyle k\leq {\frac {1}{2}}(m-1)(m+2)}$para cualquier multiplicidad de valores propios de a menos que sea un gráfico multipartito completo. ${\displaystyle m>1}$ ${\displaystyle G,}$ ${\displaystyle G}$
• ${\displaystyle d\leq 3m-4}$para cualquier multiplicidad de valores propios de a menos que sea un gráfico de ciclo o un gráfico multipartito completo. ${\displaystyle m>1}$ ${\displaystyle G,}$ ${\displaystyle G}$

Si es fuertemente regular , entonces y . ${\displaystyle G}$ ${\displaystyle n\leq 4m-1}$ ${\displaystyle k\leq 2m-1}$

Ejemplos

El gráfico de Klein de grado 7 y el mapa asociado incrustados en una superficie orientable del género 3. Este gráfico es regular en distancia con una matriz de intersección {7,4,1;1,2,7} y un grupo de automorfismo PGL(2,7).

Algunos primeros ejemplos de gráficos de distancia regular incluyen:

• Los gráficos completos .
• Los gráficos del ciclo .
• Los gráficos impares .
• Los gráficos de Moore .
• El gráfico de colinealidad de un polígono cercano regular .
• El gráfico de Wells y el gráfico de Sylvester .
• Gráficos de diámetro fuertemente regulares . ${\displaystyle 2}$

Clasificación de gráficos de distancia regular.

Sólo hay un número finito de gráficos de distancia regulares conectados distintos de cualquier valencia dada . ^[1] ${\displaystyle k>2}$

De manera similar, solo hay un número finito de gráficos de distancia regulares conectados distintos con cualquier multiplicidad de valores propios dada ^[2] (con la excepción de los gráficos multipartitos completos). ${\displaystyle m>2}$

Gráficos cúbicos de distancia regular

Las gráficas cúbicas de distancia regular se han clasificado por completo.

Las 13 gráficas cúbicas regulares de distancia distintas son K 4 (o gráfica tetraédrica ), K _3,3 , la gráfica de Petersen , la gráfica cúbica , la gráfica de Heawood , la gráfica de Pappus , la gráfica de Coxeter , la gráfica de Tutte-Coxeter , la gráfica dodecaédrica gráfico , el gráfico de Desargues , Tutte 12-cage , el gráfico de Biggs-Smith y el gráfico de Foster .

Referencias

1. Explosión, S.; Dubickas, A.; Koolen, JH; Moulton, V. (10 de enero de 2015). "Sólo hay un número finito de gráficos de distancia regular de valencia fija mayor que dos". Avances en Matemáticas . 269 ​​(Suplemento C): 1–55. arXiv : 0909.5253 . doi : 10.1016/j.aim.2014.09.025 . S2CID  18869283.
2. Godsil, CD (1 de diciembre de 1988). "Limitar el diámetro de gráficos de distancia regular". Combinatoria . 8 (4): 333–343. doi :10.1007/BF02189090. ISSN  0209-9683. S2CID  206813795.

Otras lecturas

• Godsil, CD (1993). Combinatoria Algebraica . Serie de Matemáticas de Chapman y Hall. Nueva York: Chapman y Hall. ISBN 978-0-412-04131-0. SEÑOR  1220704.