• Source: Windmill graph

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 Kk at a shared universal vertex. That is, it is a 1-clique-sum of these complete graphs.




Properties


It has n(k – 1) + 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.




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

∏

i
=
1


k
−
1


(
x
−
i

)

n


.


{\displaystyle x\prod _{i=1}^{k-1}(x-i)^{n}.}


The windmill graph Wd(k,n) is proved not graceful if k > 5. In 1979, Bermond has conjectured that Wd(4,n) is graceful for all n ≥ 4. Through an equivalence with perfect difference families, this has been proved for n ≤ 1000.

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. The windmill Wd(3,n) is graceful if and only if n ≡ 0 (mod 4) or n ≡ 1 (mod 4).




Gallery






References

Kata Kunci Pencarian:

• Windmill graph
• Friendship graph
• Glossary of graph theory
• List of graphs
• Chordal graph
• Perfect graph
• Block graph
• 1000 (number)
• Kotzig's conjecture
• Geodetic graph