Graphe moulin
From Wikipedia, the free encyclopedia
| Graphe moulin | |
.svg?lang=fr) 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 Kk à un sommet universel partagé. Autrement dit, il s'agit d'une somme, sur une clique à 1 seul sommet, de ces n graphes complets[1].
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é Fn),
- Wd(2,n) est le graphe étoile (aussi noté Sn),
- Wd(3,2) est le graphe papillon.
