Graphe de conférence
Dans le domaine mathématique de la théorie des graphes, un graphe de conférence est un graphe fortement régulier particulier.
Définition modifier
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
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.
Description modifier
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 :
chacune avec une multiplicité (v − 1)/2.
Notes et références modifier
- Andries Brouwer, A. M. Cohen et A. Neumaier, Distance Regular Graphs, Springer-Verlag, (ISBN 0-387-50619-5).
- Chris Godsil et Gordon F. Royle, Algebraic Graph Theory, Springer, coll. « Graduate Texts in Mathematics » (no 207), (1re éd. 2001) (ISBN 978-1-4613-0163-9), p. 118–123.
Liens externes modifier
- (en) Eric W. Weisstein, « Conference Graph », sur MathWorld
