Windmill graph

Vertices

n (k - 1) + 1

Edges

.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠nk(k − 1)/2⁠

Radius1

Diameter2

Windmill graph
The Windmill graph $Wd(5,4)$ .
Vertices	$n (k - 1) + 1$
Edges	$.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠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 \geq 2$ and $n \geq 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.

Special cases

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.

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$ .^[3] In 1979, Bermond has conjectured that $Wd(4, n)$ is graceful for all $n \geq 4$ .^[4] Through an equivalence with perfect difference families, this has been proved for $n \leq 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 \equiv 0 (mod 4)$ or $n \equiv 1 (mod 4)$ .^[7]

Special cases

Labeling and colouring

Gallery

References

Related Articles