Gráfica de distancia regular

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 .

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})}$${\estilo de visualización d}$${\displaystyle 1\leq j\leq d}$$Estilo de visualización b_ {j}}$${\estilo de visualización u}$${\estilo de visualización j+1}$${\estilo de visualización v}$$Estilo de visualización c_ {j}}$${\estilo de visualización u}$${\estilo de visualización j-1}$${\estilo de visualización v}$${\estilo de visualización u}$${\estilo de visualización v}$${\estilo de visualización j}$$estilo de visualización a_ {j}}$${\estilo de visualización u}$${\estilo de visualización j}$${\estilo de visualización 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}$

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.

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}$

• ${\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}}$

• ${\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}$

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}$

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}$

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

Los 13 grafos cúbicos regulares de distancia distintos son K ₄ (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 .

• 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  .