Grafo fortemente regular

Famílias de grafos definidos por seus automorfismos
distância-transitivo	$\to$	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	$\to$	aresta-transitivo e regular	$\to$	aresta-transitivo
$\downarrow$		$\downarrow$
vértice-transitivo	$\to$	regular
$\uparrow$
grafo de Cayley		antissimétrico		assimétrico

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}[(\lambda -\mu )+\sqrt{(\lambda -\mu {)}^2+4(k-\mu )}]$ cuja multiplicidade é $\frac{1}{2}[(v-1)-\frac{2k+(v-1)(\lambda -\mu )}{\sqrt{(\lambda -\mu {)}^2+4(k-\mu )}}]$
  • $\frac{1}{2}[(\lambda -\mu )-\sqrt{(\lambda -\mu {)}^2+4(k-\mu )}]$ cuja multiplicidade é $\frac{1}{2}[(v-1)+\frac{2k+(v-1)(\lambda -\mu )}{\sqrt{(\lambda -\mu {)}^2+4(k-\mu )}}]$
• 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(v,\frac{v-1}{2},\frac{v-5}{4},\frac{v-1}{4})$.
• Grafos fortemente regulares para os quais $2k+(v-1)(\lambda -\mu )\ne 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², 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

• 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

Ligações externas

• Eric W. Weisstein, Mathworld artigo com numerosos exemplos.
• Gordon Royle, Lista dos maiores grafos e famílias.
• Andries E. Brouwer, Parametros de grafos fortemente regulares.