Grafo distância-regular
De Wikipedia, a enciclopédia encyclopedia
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.
Alternativamente, um grafo distância-regular é um grafo para o qual existem inteiros bi,ci,i=0,...,d tais que para quaisquer dois vértices x, y em G e distância i=d(x,y), há exatamente ci vizinhos de y em Gi-1(x) e bi vizinhos de y em Gi+1(x), onde Gi(x) é o conjunto de vértices y de G com d(x,y)=i (Brouwer et al. 1989, p. 434).[1] 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).