Grafo fortemente regular
Aspeto
Grafo fortemente regular | |
---|---|
O Grafo Paley de ordem 13, um grafo fortemente regular com parâmetros gfr(13,6,2,3).
|
Na teoria dos grafos, uma disciplina dentro da matemática, um grafo fortemente regular é definido como se segue. Seja G = (V,E) um grafo regular com v vértices e grau k. G é dito ser fortemente regular se houver também inteiros λ e μ tais que:
- Cada dois vértices adjacentes tem λ vizinhos em comum.
- Cada dois vértices não-adjacentes tem μ vizinhos em comum.
Um grafo deste tipo é dito às vezes ser um gfr(v,k,λ,μ).
Alguns autores excluem grafos que satisfazem a definição trivial, ou seja, os grafos que são a união disjunta de um ou mais grafos completos de tamanho igual, e os seus complementares, os grafos de Turan.
Um grafo fortemente regular é um grafo distância-regular com diâmetro 2, mas somente se μ não é zero.
Propriedades
[editar | editar código-fonte]- Os quatro parãmetros em um grs(v,k,λ,μ) não são independentes, como é fácil mostrar que:
- Seja I denotando a matriz identidade (de ordem v) e faça-se J denotar a matriz cujas entradas são todas iguais a 1. A matriz de adjacência A de um grafo fortemente regular satisfaz as seguintes propriedades:
(Esta é uma reafirmação trivial da exigência para os graus de vértices).
(O primeiro termo indica o número de caminhos de 2-passos de cada vértice para todos os vértices. Para os pares de vértices diretamente ligados por uma aresta, a equação reduz-se o número de tais caminhos em 2 passos sendo igual a . Para os pares de vértices não directamente ligados por uma aresta, a equação reduz-se ao número de tais caminhos em 2 passos sendo igual a . Para os auto-pares triviais, a equação reduz-se para o grau igual a k).
- O grafo tem exatamente três autovalores:
- cuja multiplicidade é 1
- cuja multiplicidade é
- cuja multiplicidade é
- Grafos fortemente regulares para os quais são chamados grafos de conferência devido a sua conexão com matrizes de conferência simétricas. Seus parâmetros se reduzem a.
- Grafos fortemente regulares para os quais tem autovalores inteiros com multiplicidades desiguais.
- O complemento de um gfr(v,k,λ,μ) também é fortemente regular. É um gfr(v, v−k−1, v−2−2k+μ, v−2k+λ)
Exemplos
[editar | editar código-fonte]- O grafo de Shrikhande é um gfr(16,6,2,2) que não é um grafo distância-transitivo.
- O ciclo de comprimento 5 é um gfr(5,2,0,1).
- O grafo de Petersen é um gfr(10,3,0,1).
- Os grafos de Chang são gfr(28,12,6,4).
- O grafo de Hoffman–Singleton é um gfr(50,7,0,1).
- O grafo de Higman–Sims é um gfr(100,22,0,4).
- Os grafos de Paley de ordem q são gfr(q, (q − 1)/2, (q − 5)/4, (q − 1)/4.
- O grafo de rook quadrado n × n é um gfr(n2, 2n − 2, n − 2, 2).
- O grafo de Brouwer–Haemers é um gfr(81,20,1,6).
- O grafo de Schläfli é um gfr(27,16,10,8).
Bibliografia
[editar | editar código-fonte]- A.E. Brouwer, A.M. Cohen, and A. Neumaier (1989), Distance Regular Graphs. Berlin, New York: Springer-Verlag. ISBN 3-540-50619-5, ISBN 0-387-50619-5
- Chris Godsil and Gordon Royle (2004), Algebraic Graph Theory. New York: Springer-Verlag. ISBN 0-387-95241-1