The Windmill graph Wd(5,4).
|Girth||3 if k > 2|
In the mathematical field of graph theory, the windmill graph Wd(k,n) is an undirected graph constructed for k ≥ 2 and n ≥ 2 by joining n copies of the complete graph Kk at a shared vertex. That is, it is a 1-clique-sum of these complete graphs.
It has (k-1)n+1 vertices and nk(k−1)/2 edges, girth 3 (if k > 2), radius 1 and diameter 2. It has vertex connectivity 1 because its central vertex is an articulation point; however, like the complete graphs from which it is formed, it is (k-1)-edge-connected. It is trivially perfect and a block graph.
Labeling and colouring
The windmill graph Wd(k,n) is proved not graceful if k > 5. In 1979, Bermond has conjectured that Wd(4,n) is graceful for all n ≥ 4. This is known to be true for n ≤ 22. Bermond, Kotzig, and Turgeon proved that Wd(k,n) is not graceful when k = 4 and n = 2 or n = 3, and when k = 5 and m = 2. The windmill Wd(3,n) is graceful if and only if n ≡ 0 (mod 4) or n ≡ 1 (mod 4).
Gallery↑Jump back a section
- Gallian, J. A. "Dynamic Survey DS6: Graph Labeling." Electronic J. Combinatorics, DS6, 1-58, Jan. 3, 2007. .
- Weisstein, Eric W., "Windmill Graph", MathWorld.
- K. M. Koh, D. G. Rogers, H. K. Teo, and K. Y. Yap, Graceful graphs: some further results and problems, Congr. Numer., 29 (1980) 559-571.
- J.C. Bermond, Graceful graphs, radio antennae and French windmills, Graph Theory and Combinatorics, Pitman, London (1979) 18-37.
- J. Huang and S. Skiena, Gracefully labeling prisms, Ars Combin., 38 (1994) 225- 242.
- J. C. Bermond, A. Kotzig, and J. Turgeon, On a combinatorial problem of antennas in radioastronomy, in Combinatorics, A. Hajnal and V. T. Sos, eds., Colloq. Math. Soc. János Bolyai, 18, 2 vols. North-Holland, Amsterdam (1978) 135-149.
- J.C. Bermond, A. E. Brouwer, and A. Germa, "Systèmes de triplets et différences associées", Problèmes Combinatoires et Théorie des Graphes, Colloq. Intern. du CNRS, 260, Editions du Centre Nationale de la Recherche Scientifique, Paris (1978) 35-38.