Windmill graph

Windmill graph
The Windmill graph Wd(5,4).
Vertices	(k-1)n+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)

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 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.

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 form the chromatic polynomial of the complete graph and is equal to ${\displaystyle \prod _{i=0}^{k-1}(x-i)^{n}.}$