Windmill graph

Windmill graph
The Windmill graph Wd(5,4).
Vertices	n(k − 1) + 1
Edges	⁠nk(k − 1)/2⁠
Radius	1
Diameter	2
Girth	3 if k > 2
Chromatic number	k
Chromatic index	n(k − 1)
Notation	Wd(k,n)
Table of graphs and parameters

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

It has n(k − 1) + 1 vertices and nk(k − 1)/2 edges,^[2] 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.

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

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

${\displaystyle x\prod _{i=1}^{k-1}(x-i)^{n}.}$

The windmill graph Wd(k,n) is proved not graceful if k > 5.^[3] In 1979, Bermond has conjectured that Wd(4,n) is graceful for all n ≥ 4.^[4] Through an equivalence with perfect difference families, this has been proved for n ≤ 1000. ^[5] 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 n = 2.^[6] The windmill Wd(3,n) is graceful if and only if n ≡ 0 (mod 4) or n ≡ 1 (mod 4).^[7]