Windmill graph

---

title: "Windmill graph" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["parametric-families-of-graphs", "perfect-graphs"] description: "Graph family made by joining complete graphs at a universal node" topic_path: "general/parametric-families-of-graphs" source: "https://en.wikipedia.org/wiki/Windmill_graph" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Graph family made by joining complete graphs at a universal node ::

::data[format=table title="infobox graph"]

Field	Value
name	Windmill graph
image	[[Image:Windmill graph Wd(5,4).svg
image_caption	The Windmill graph Wd(5,4).
vertices	n(k − 1) + 1
edges
girth	3 if k 2
diameter	2
radius	1
chromatic_number	k
chromatic_index	n(k − 1)
notation	Wd(k,n)
::

| name = Windmill graph | image = [[Image:Windmill graph Wd(5,4).svg|220px]] | image_caption = The Windmill graph Wd(5,4). | vertices = n(k − 1) + 1 | edges = | automorphisms = | girth = 3 if k 2 | diameter = 2 | radius = 1 | chromatic_number = k | chromatic_index = n(k − 1) |notation = Wd(k,n) | properties =

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 K at a shared universal vertex. That is, it is a 1-clique-sum of these complete graphs.

Properties

It has n(k − 1) + 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.

Special cases

By construction, the windmill graph Wd(3,n) is the friendship graph F, the windmill graph Wd(2,n) is the star graph S and the windmill graph Wd(3,2) is the butterfly graph.

Labeling and colouring

The windmill graph has chromatic number k and chromatic index n(k − 1). Its chromatic polynomial can be deduced from the chromatic polynomial of the complete graph and is equal to :x\prod_{i=1}^{k-1}(x-i)^n.

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. Through an equivalence with perfect difference families, this has been proved for n ≤ 1000. Bermond, Kotzig, and Turgeon proved that Wd(k,n) is not graceful when and or , and when and . The windmill Wd(3,n) is graceful if and only if n ≡ 0 (mod 4) or n ≡ 1 (mod 4).

Gallery

::figure[src="https://upload.wikimedia.org/wikipedia/commons/2/28/Windmill_graphs.svg" caption="Small windmill graphs."] ::

References

References

1. Gallian, J. A.. (3 January 2007). "A dynamic survey of graph labeling". Electronic Journal of Combinatorics.
2. "Windmill Graph".
3. (1980). "Graceful graphs: some further results and problems". Congressus Numerantium.
4. Bermond, J.-C.. (1979). "Graph theory and combinatorics (Proc. Conf., Open Univ., Milton Keynes, 1978)". Pitman.
5. (2010). "Perfect difference families, perfect difference matrices, and related combinatorial structures". Journal of Combinatorial Designs.
6. (1978). "Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I". North-Holland.
7. (1978). "Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976)". Éditions du Centre national de la recherche scientifique.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::