Windmill graph

[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 is trivially perfect and a block graph.

Its chromatic polynomial can be deduced from the chromatic polynomial of the complete graph and is equal to The windmill graph Wd(k,n) is proved not graceful if k > 5.

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

Small windmill graphs.