Windmill graph
Windmill graph | ||
---|---|---|
Chromatic index n(k – 1) | | |
Notation | Wd(k,n) | |
Table of graphs and parameters |
In the
Properties
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 Fn, the windmill graph Wd(2,n) is the star graph Sn and the windmill graph Wd(3,2) is the butterfly graph.
Labeling and colouring
The windmill graph has
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]
Gallery
References
- MR 1668059.
- ^ Weisstein, Eric W. "Windmill Graph". MathWorld.
- MR 0608456.
- OCLC 757210583.
- S2CID 120800012.
- MR 0519261.
- MR 0539936.