Graphe de conférence

Un graphe de conférence est un graphe fortement régulier dont les paramètres (v,k,λ,μ) liés au nombre v de ses somments sont :

• le degré de ses sommets est k = (v − 1)/2,
• le nombre λ de voisins communs à toute paire de sommets adjacentsest λ = (v − 5)/4,
• le nombre μ de voisins communs à toute paire de sommets non adjacents est μ = (v − 1)/4..

Leur type est donc

${\displaystyle (v,(v-1)/2,(v-5)/4,(v-1)/4)}$

C'est le graphe associé à une matrice de conférence symétrique, et par conséquent son ordre v doit être égal à 1 ( modulo 4) et être la somme de deux carrés.

On connaît les graphes de conférence pour les petites valeurs de v permises par les restrictions, par exemple pour v = 5, 9, 13, 17, 25, 29, et (les graphes de Paley) pour toutes les puissances de nombres premiers congruentes à 1 (modulo 4) . Cependant, de nombreuses valeurs de v sont admissibles pour lesquelles l'existence d'un graphe de conférence est inconnue. Les graphes de Paley sont tous des graphes de conférence.

Les valeurs propres d'un graphe de conférence ne sont pas nécessairement des entiers, contrairement à celles d'autres graphes fortement réguliers. Si le graphe est connexe, les valeurs propres sont l'entier k avec multiplicité 1, et deux les deux autres valeurs :

${\displaystyle {\frac {-1\pm {\sqrt {v}}}{2}},}$

chacune avec une multiplicité (v − 1)/2.

• Andries Brouwer, A. M. Cohen et A. Neumaier, Distance Regular Graphs, Springer-Verlag, 1989 (ISBN 0-387-50619-5).
• Chris Godsil et Gordon F. Royle, Algebraic Graph Theory, Springer, coll. « Graduate Texts in Mathematics » (n^o 207), 2013 (1^re éd. 2001) (ISBN 978-1-4613-0163-9), p. 118–123.

• (en) Eric W. Weisstein, « Conference Graph », sur MathWorld

• Portail des mathématiques
• Portail de l'informatique théorique