Graphe moulin

Modèle:Infobox Graphe 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 K_k à 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é F_n),
• Wd(2,n) est le graphe étoile (aussi noté S_n),
• 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 à $x\prod _{i=1}^{k-1}(x-i{)}^n.$

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

Petits graphes moulin