Gráfico de distancia regular

En matemáticas , un gráfico de distancia regular es un gráfico regular tal que para dos vértices cualesquiera v y w , el número de vértices a una distancia j de vy a una distancia k de w depende solo de j , k e i = d (v , w) .

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

Resulta que una gráfica de diámetro es regular a la distancia si y solo si hay una matriz de enteros tal que para todos , 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 a una distancia en . La matriz de números enteros que caracteriza a un gráfico de distancia regular se conoce como matriz de intersección .${\ Displaystyle G}$${\ Displaystyle d}$${\ Displaystyle \ {b_ {0}, b_ {1}, \ ldots, b_ {d-1}; c_ {1}, \ ldots, c_ {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 G}$

Un par de gráficos regulares de distancia conectados son cospectrales si y solo si tienen la misma matriz de intersección.

Un gráfico regular a distancia se desconecta si y solo si es una unión disjunta de gráficos regulares a distancia cospectral.

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