Windmill graph
Template:Short description Template:Infobox graph
In the mathematical field of graph theory, the windmill graph Template:Math is an undirected graph constructed for Template:Math and Template:Math by joining Template:Mvar copies of the complete graph Template:Mvar at a shared universal vertex. That is, it is a 1-clique-sum of these complete graphs.[1]
Properties
It has Template:Math vertices and Template:Math edges,[2] girth 3 (if Template:Math), 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 Template:Math-edge-connected. It is trivially perfect and a block graph.
Special cases
By construction, the windmill graph Template:Math is the friendship graph Template:Mvar, the windmill graph Template:Math is the star graph Template:Mvar and the windmill graph Template:Math is the butterfly graph.
Labeling and colouring
The windmill graph has chromatic number Template:Mvar and chromatic index Template:Math. Its chromatic polynomial can be deduced from the chromatic polynomial of the complete graph and is equal to
The windmill graph Template:Math is proved not graceful if Template:Math.[3] In 1979, Bermond has conjectured that Template:Math is graceful for all Template:Math.[4] Through an equivalence with perfect difference families, this has been proved for Template:Math. [5] Bermond, Kotzig, and Turgeon proved that Template:Math is not graceful when Template:Math and Template:Math or Template:Math, and when Template:Math and Template:Math.[6] The windmill Template:Math is graceful if and only if Template:Math or Template:Math.[7]
