Graphe moulin

Graphe moulin
Graphe moulin Wd(5,4)
Notation	Wd(k,n)
Nombre de sommets	(k − 1) n + 1
Nombre d'arêtes	nk (k − 1) / 2
Maille	3 (pour k > 2)
Nombre chromatique	k
Indice chromatique	n (k − 1)
modifier

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[1].

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[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 à ${\displaystyle x\prod _{i=1}^{k-1}(x-i)^{n}.}$

Le graphe moulin Wd(k,n) n'est pas gracieux pour k > 5[3]. En 1979, Jean-Claude Bermond a conjecturé que Wd(4,n) est gracieux pour tout n ≥ 4[4]. Par une équivalence avec des familles parfaites de différences, elle a été vérifiée pour n ≤ 1000[5]. 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[6]. Le graphe Wd(3,n) est gracieux si et seulement si n ≡ 0 (mod 4) ou n ≡ 1 (mod 4)[7].

Galerie

Petits graphes moulin

---

Références

1. Joseph A. Gallian, « A dynamic survey of graph labeling », Electronic Journal of Combinatorics, vol. DS6,‎ 3 janvier 2007, p. 1–58 (MR 1668059, lire en ligne).
2. (en) Eric W. Weisstein, « Windmill Graph », sur MathWorld.
3. K. M. Koh, D. G. Rogers, H. K. Teo et K. Y. Yap, « Graceful graphs: some further results and problems », Congressus Numerantium, vol. 29,‎ 1980, p. 559–571 (MR 0608456).
4. J.-C. Bermond, « Graceful graphs, radio antennae and French windmills », dans Robin J. Wilson (éditeur), Graph theory and combinatorics (Proc. Conf., Open Univ., Milton Keynes, 1978), Pitman, coll. « Research notes in mathematics » (n^o 34), 1979 (ISBN 978-0273084358, OCLC 757210583, MR 0587620), p. 18–37.
5. Gennian Ge, Ying Miao et Xianwei Sun, « Perfect difference families, perfect difference matrices, and related combinatorial structures », Journal of Combinatorial Designs, vol. 18, n^o 6,‎ 2010, p. 415–449 (DOI 10.1002/jcd.20259, MR 2743134).
6. J.-C. Bermond, A. Kotzig et J. Turgeon, « On a combinatorial problem of antennas in radioastronomy », dans A. Hajnal et Vera T. Sos (éditeurs), Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, North-Holland, coll. « Colloquia mathematica Societatis János Bolyai » (n^o 18), 1978 (ISBN 978-0-444-85095-9, MR 0519261), p. 135–149.
7. J.-C. Bermond, A. E. Brouwer et A. Germa, « Systèmes de triplets et différences associées », dans Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Éditions du Centre national de la recherche scientifique, coll. « Colloques internationaux du Centre National de la Recherche Scientifique » (n^o 260), 1978 (ISBN 978-2-222-02070-7, MR 0539936), p. 35–38.