Grafo distância-regular

No campo da matemática da teoria dos grafos, um grafo distância-regular é um grafo regular tal que para quaisquer dois vértices v e w a uma distância i o número de vértices adjacentes a w e à distância j a partir de v é o mesmo. Todo grafo distância-transitivo é distância regular. Com efeito, grafos distância-regular foram introduzidos como uma generalização combinatória de grafos distância-transitivos, tendo as propriedades de regularidade numérica do último, sem ter necessariamente um grande grupo de automorfismo.

O grafo de Shrikhande, um grafo distância-regular.

Famílias de grafos definidos por seus automorfismos
distância-transitivo	$\rightarrow$	distância-regular	$\leftarrow$	fortemente regular
$\downarrow$
simétrico (arco-transitivo)	$\leftarrow$	t-transitivo, t ≥ 2		.
$\downarrow$ (se conectado)
transitivo nos vértices e nas arestas	$\rightarrow$	aresta-transitivo e regular	$\rightarrow$	aresta-transitivo
$\downarrow$		$\downarrow$
vértice-transitivo	$\rightarrow$	regular
$\uparrow$
grafo de Cayley		antissimétrico		assimétrico

Alternativamente, um grafo distância-regular é um grafo para o qual existem inteiros b_i,c_i,i=0,...,d tais que para quaisquer dois vértices x, y em G e distância i=d(x,y), há exatamente c_i vizinhos de y em G_i-1(x) e b_i vizinhos de y em G_i+1(x), onde G_i(x) é o conjunto de vértices y de G com d(x,y)=i (Brouwer et al. 1989, p. 434). O array de inteiros caracterizando um grafo distância regular é conhecido como o seu array de interseção.

Um grafo distância-regular com diâmetro 2 é fortemente regular, e reciprocamente (a menos que o grafo seja desconexo).

Números Intersecção

É usual utilizar a seguinte notação para um grafo distância-regular G. O número de vértices é n. O número de vizinhos de w (Isto é, os vértices adjacentes a w) cuja distância de v é i, i + 1, e i − 1 é denotada por a_i, b_i, e c_i, respectivamente; estes são os números de intersecção de G. Obviamente, a₀ = 0, c₀ = 0, e b₀ é igual a k, o grau de qualquer vértice. Se G tem um diâmetro finito, então d denota o diâmetro enós temos b_d = 0. Também temos que a_i+b_i+c_i= k

Os numeros a_i, b_i, e c_i são frequentemente mostrados em um array de três linhas.

$\left\{{\begin{matrix}-&c_{1}&\cdots &c_{d-1}&c_{d}\\a_{0}&a_{1}&\cdots &a_{d-1}&a_{d}\\b_{0}&b_{1}&\cdots &b_{d-1}&-\end{matrix}}\right\},$

chamado o array de intersecção de G. Eles podem ser formados também por uma matriz tridiagonal

$B:={\begin{pmatrix}a_{0}&b_{0}&0&\cdots &0&0\\c_{1}&a_{1}&b_{1}&\cdots &0&0\\0&c_{2}&a_{2}&\cdots &0&0\\\vdots &\vdots &\vdots &&\vdots &\vdots \\0&0&0&\cdots &a_{d-1}&b_{d-1}\\0&0&0&\cdots &c_{d}&a_{d}\end{pmatrix}},$

chamada de matriz de intersecção.

Matrizes de adjacência distância

Suponha que G é um grafo distância-regular conexo. Para cada distância i = 1, ..., d, podemos formar um grafo G_i no qual os vértices são adjacentes se sua distância em G é igual a i. Façamos A_i ser a matriz de adjacência de G_i. Por exemplo, A₁ é a matriz de adjacência A de G. Além disso, seja A₀ = I, a matriz identidade. Isto nos dá d + 1 matrizes A₀, A₁, ..., A_d, chamadas as matrizes de distância de G. A soma é a matriz J em que cada entrada é 1. Há uma fórmula de produto importante:

$AA_{i}=a_{i}A_{i}+b_{i}A_{i+1}+c_{i}A_{i-1}.$

A partir desta fórmula resulta que cada A_i é uma função polinomial de A, de grau i, e que A satisfaz um polinômio de grau d + 1. Além disso, A tem exatamente d + 1 autovalores distintos, dos quais o maior é k, o grau.

As matrizes de distância abrangem um subespaço vetorial do espaço vetorial de todas n × n matrizes reais. É um fato notável que o produto A_i A_j de quaisquer duas matrizes de distância é uma combinação linear das matrizes de distância:

$A_{i}A_{j}=\sum _{k=0}^{d}p_{ij}^{k}A_{k}.$

Isto significa que as matrizes de distância geram um esquema de associação. A teoria dos esquemas de associação é fundamental para o estudo dos gráficos de distância regular. Por exemplo, o fato de que A_i é uma função polinomial de A é um fato sobre os esquemas de associação.

Exemplos

• Grafos completos são distância regular com diâmetro 1 e grau v−1.
• Ciclos C_2d+1 de comprimento ímpar são distância regular com k = 2 e diâmetro d. Os números de intersecção a_i = 0, b_i = 1, e c_i = 1, exceto para os casos usuais especiais (ver acima) e c_d = 2.
• Todos os grafos de Moore, em particular o grafo de Petersen e o grafo de Hoffman–Singleton, são distância regulares.
• grafos fortemente regulares são distância regular.
• Grafos ímpares são distância regular.