Grafo regular de distancia

En el campo matemático de la teoría de grafos , un grafo distancia-regular es un grafo regular tal que para cualesquiera dos vértices v y w , el número de vértices a distancia j de v y a distancia k de w depende solo 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 distancia es regular en distancia. De hecho, los grafos regulares en distancia se introdujeron como una generalización combinatoria de los grafos transitivos en distancia, que poseen las propiedades de regularidad numérica de estos últimos sin necesidad de tener un grupo de automorfismos grande .

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

Resulta que un gráfico${\displaystyle G}$de diámetro${\displaystyle d}$Una distancia es regular si y solo si tiene una matriz de intersección en el sentido anterior.

Un par de grafos regulares de distancia conectados son coespectrales si sus matrices de adyacencia tienen el mismo espectro . Esto es equivalente a que tengan la misma matriz de intersección.

Un grafo distancia-regular es desconectado si y solo si es una unión disjunta de grafos distancia-regulares coespectrales.

Suponer${\displaystyle G}$es un grafo de valencia conectado y regular en cuanto a distancia${\displaystyle k}$con matriz de intersección${\displaystyle (b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d})}$. Para cada${\displaystyle 0\leq j\leq d,}$dejar${\displaystyle k_{j}}$denota el número de vértices a distancia${\displaystyle j}$desde cualquier vértice dado y sea ${\displaystyle G_{j}}$denotan el${\displaystyle k_{j}}$-grafo regular con matriz de adyacencia${\displaystyle A_{j}}$formado al relacionar pares de vértices en${\displaystyle G}$a distancia${\displaystyle j}$.

Algunos primeros ejemplos de grafos regulares en distancia incluyen:

• Los gráficos completos .
• Los gráficos cíclicos .
• Los gráficos extraños .
• Los gráficos de Moore .
• El gráfico de colinealidad de un polígono casi regular .
• El gráfico de Wells y el gráfico de Sylvester .
• Los grafos fuertemente regulares son los grafos distancia-regulares de diámetro 2.

Solo hay un número finito de grafos regulares de distancia conectados distintos de cualquier valencia dada.${\displaystyle k>2}$. ^{[ 1 ]}

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

• Godsil, C.  D. (1993). Combinatoria algebraica . Serie de matemáticas de Chapman and Hall. Nueva York: Chapman and Hall. ISBN 978-0-412-04131-0MR 1220704 .​