Gráfica de distancia regular

Propiedad gráfica

En el campo matemático de la teoría de grafos , un grafo regular en distancia es un grafo regular tal que para cualesquiera dos vértices v y w , el número de vértices a una distancia j de v y a una distancia k de w depende únicamente de j , k y la distancia entre v y w .

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

Todo grafo transitivo en función de la distancia es regular en función de la distancia. De hecho, los grafos regulares en función de la distancia se introdujeron como una generalización combinatoria de los grafos transitivos en función de la distancia, ya que poseen las propiedades de regularidad numérica de estos últimos sin tener necesariamente un gran grupo de automorfismos .

Matrices de intersección

La matriz de intersección de un grafo regular-distante es la matriz en la que es el diámetro del grafo y para cada , da el número de vecinos de a una distancia de y da el número de vecinos de a una distancia de para cualquier par de vértices y a una distancia . También existe el número que da el número de vecinos de a una distancia de . Los números se denominan números de intersección del grafo. Satisfacen la ecuación donde es 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 un gráfico de diámetro es regular en distancia si y sólo si tiene una matriz de intersecciones en el sentido anterior. ${\displaystyle G}$ ${\displaystyle d}$

Gráficas regulares de distancia coespectrales y desconectadas

Un par de grafos regulares conexos son coespectrales si sus matrices de adyacencia tienen el mismo espectro . Esto es equivalente a que tengan la misma matriz de intersecciones.

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

Propiedades

Supóngase que es un grafo regular-distante conexo de valencia con matriz de intersección . Para cada sea el número de vértices a una distancia de cualquier vértice dado y sea el grafo regular-distante con matriz de adyacencia formado al relacionar pares de vértices en una 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 es o ambos y si 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 están incrustados en una superficie orientable de 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 automorfismos PGL(2,7).

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

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

Clasificación de grafos regulares-distantes

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

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

Gráficas regulares de distancia cúbica

Los gráficos cúbicos de distancia-regulares han sido completamente clasificados.

Los 13 grafos cúbicos regulares de distancia distintos son K 4 (o grafo tetraédrico ), K _3,3 , el grafo de Petersen , el grafo cúbico , el grafo de Heawood , el grafo de Pappus , el grafo de Coxeter , el grafo de Tutte-Coxeter , el grafo dodecaédrico , el grafo de Desargues , el grafo de 12 jaulas de Tutte , el grafo de Biggs-Smith y el grafo de Foster .

Referencias

1. Bang, S.; Dubickas, A.; Koolen, JH; Moulton, V. (10 de enero de 2015). "Sólo hay un número finito de grafos regulares en función de la distancia con 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 (1988-12-01). "Acotación del diámetro de grafos regulares en función de la distancia". Combinatorica . 8 (4): 333–343. doi :10.1007/BF02189090. ISSN  0209-9683. S2CID  206813795.

Lectura adicional

• Godsil, C. D. (1993). Combinatoria algebraica . Chapman and Hall Mathematics Series. Nueva York: Chapman and Hall. ISBN 978-0-412-04131-0.Señor 1220704  .