# Grafo fortemente regular

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

* Os quatro parãmetros em um grs(v,k,λ,μ) não são independentes, como é fácil mostrar que:
    $(v-k-1)\mu =k(k-\lambda -1)$
* 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:
** $A\times J=kJ$ (Esta é uma reafirmação trivial da exigência para os graus de vértices).
** ${A}^{2}+(\mu -\lambda ){A}+(\mu -k){I}=\mu {J}$ (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 $\lambda$. 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 $\mu$. Para os auto-pares triviais, a equação reduz-se para o grau igual a k).
* O grafo tem exatamente três autovalores:
** $k$ cuja multiplicidade é 1
** ${\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right]$ cuja multiplicidade é ${\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$
** ${\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right]$ cuja multiplicidade é ${\frac {1}{2}}\left[(v-1)+{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]$
* Grafos fortemente regulares para os quais $2k+(v-1)(\lambda -\mu )=0$ 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$srg\left(v,{\frac {v-1}{2}},{\frac {v-5}{4}},{\frac {v-1}{4}}\right)$.
* Grafos fortemente regulares para os quais $2k+(v-1)(\lambda -\mu )\neq 0$ 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

* 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(n$^2$, 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).