En théorie des graphes, le graphe moulin Wd(k,n) est un graphe non orienté construit, pour deux entiers k ≥ 2 et n ≥ 2, en joignant n copies du graphe complet Kk à un sommet universel partagé. Autrement dit, il s'agit d'une somme, sur une clique à 1 seul sommet, de ces n graphes complets..
Propriétés Le graphe moulin Wd(k,n) a (k−1) n + 1 sommets et nk (k − 1) / 2 arêtes, il est de maille 3 (pour k > 2), de rayon 1 et de diamètre 2.. Il est 1-sommet-connexe parce que son sommet central est un point d'articulation ; cependant, comme les graphes complets à partir desquels il est formé, il est (k−1)-arête-connexe. Il est trivialement parfait et un graphe bloc.
Cas particuliers Par construction, le graphe moulin Wd(3,n) est le graphe d'amitié ou graphe de moulin hollandais (aussi noté Fn), Wd(2,n) est le graphe étoile (aussi noté Sn), Wd(3,2) est le graphe papillon.
Étiquetage et coloration Le graphe moulin a le nombre chromatique k et l'indice chromatique n (k−1). Son polynôme chromatique peut être déduit du polynôme chromatique du graphe complet et est égal à
Le graphe moulin Wd(k,n) n'est pas gracieux pour k > 5.. En 1979, Jean-Claude Bermond a conjecturé que Wd(4,n) est gracieux pour tout n ≥ 4.. Par une équivalence avec des familles parfaites de différences, elle a été vérifiée pour n ≤ 1000.. Bermond, Kotzig et Turgeon ont prouvé que Wd(k,n) n'est pas gracieux lorsque k = 4 et n = 2 ou n = 3, et lorsque k = 5 et m = 2.. Le graphe Wd(3,n) est gracieux si et seulement si n ≡ 0 (mod 4) ou n ≡ 1 (mod 4)..
Galerie centré|vignette|550x550px| Petits graphes moulin
Références
Catégorie:Graphe parfait