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.

Grafo fortemente regular
O Grafo Paley de ordem 13, um grafo fortemente regular com parâmetros gfr(13,6,2,3).

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

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:

${\displaystyle (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:
  • ${\displaystyle A\times J=kJ}$
    (Esta é uma reafirmação trivial da exigência para os graus de vértices).
  • ${\displaystyle {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 ${\displaystyle \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 ${\displaystyle \mu }$. Para os auto-pares triviais, a equação reduz-se para o grau igual a k).
• O grafo tem exatamente três autovalores:
  • ${\displaystyle k}$ cuja multiplicidade é 1
  • ${\displaystyle {\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right]}$ cuja multiplicidade é ${\displaystyle {\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]}$
  • ${\displaystyle {\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right]}$ cuja multiplicidade é ${\displaystyle {\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 ${\displaystyle 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${\displaystyle srg\left(v,{\frac {v-1}{2}},{\frac {v-5}{4}},{\frac {v-1}{4}}\right)}$.
• Grafos fortemente regulares para os quais ${\displaystyle 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², 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.