Windmill graph

Windmill graph
Windmill graph
	The Windmill graph Wd(5,4).
Vertices	n(k – 1) 1
Edges	⁠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]

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

Gallery

References

^ Gallian, J. A. (3 January 2007). "A dynamic survey of graph labeling" (PDF). Electronic Journal of Combinatorics. DS6: 1–58. MR 1668059.
^ Weisstein, Eric W. "Windmill Graph". MathWorld.
^ Koh, K. M.; Rogers, D. G.; Teo, H. K.; Yap, K. Y. (1980). "Graceful graphs: some further results and problems". Congressus Numerantium. 29: 559–571. MR 0608456.
^ Bermond, J.-C. (1979). "Graceful graphs, radio antennae and French windmills". In Wilson, Robin J. (ed.). Graph theory and combinatorics (Proc. Conf., Open Univ., Milton Keynes, 1978). Research notes in mathematics. Vol. 34. Pitman. pp. 18–37. ISBN 978-0273084358. MR 0587620. OCLC 757210583.
^ Ge, G.; Miao, Y.; Sun, X. (2010). "Perfect difference families, perfect difference matrices, and related combinatorial structures". Journal of Combinatorial Designs. 18 (6): 415–449. doi:10.1002/jcd.20259. MR 2743134. S2CID 120800012.
^ Bermond, J.-C.; Kotzig, A.; Turgeon, J. (1978). "On a combinatorial problem of antennas in radioastronomy". In Hajnal, A.; Sos, Vera T. (eds.). Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I. Colloquia mathematica Societatis János Bolyai. Vol. 18. North-Holland. pp. 135–149. ISBN 978-0-444-85095-9. MR 0519261.
^ Bermond, J.-C.; Brouwer, A. E.; Germa, A. (1978). "Systèmes de triplets et différences associées". Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976). Colloques internationaux du Centre National de la Recherche Scientifique. Vol. 260. Éditions du Centre national de la recherche scientifique. pp. 35–38. ISBN 978-2-222-02070-7. MR 0539936.

[1] Gallian, J. A. (3 January 2007). "A dynamic survey of graph labeling" (PDF). Electronic Journal of Combinatorics. DS6: 1–58. MR 1668059.

[2] Weisstein, Eric W. "Windmill Graph". MathWorld.

[3] Koh, K. M.; Rogers, D. G.; Teo, H. K.; Yap, K. Y. (1980). "Graceful graphs: some further results and problems". Congressus Numerantium. 29: 559–571. MR 0608456.

[4] Bermond, J.-C. (1979). "Graceful graphs, radio antennae and French windmills". In Wilson, Robin J. (ed.). Graph theory and combinatorics (Proc. Conf., Open Univ., Milton Keynes, 1978). Research notes in mathematics. Vol. 34. Pitman. pp. 18–37. ISBN 978-0273084358. MR 0587620. OCLC 757210583.

[5] Ge, G.; Miao, Y.; Sun, X. (2010). "Perfect difference families, perfect difference matrices, and related combinatorial structures". Journal of Combinatorial Designs. 18 (6): 415–449. doi:10.1002/jcd.20259. MR 2743134. S2CID 120800012.

[6] Bermond, J.-C.; Kotzig, A.; Turgeon, J. (1978). "On a combinatorial problem of antennas in radioastronomy". In Hajnal, A.; Sos, Vera T. (eds.). Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I. Colloquia mathematica Societatis János Bolyai. Vol. 18. North-Holland. pp. 135–149. ISBN 978-0-444-85095-9. MR 0519261.

[7] Bermond, J.-C.; Brouwer, A. E.; Germa, A. (1978). "Systèmes de triplets et différences associées". Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976). Colloques internationaux du Centre National de la Recherche Scientifique. Vol. 260. Éditions du Centre national de la recherche scientifique. pp. 35–38. ISBN 978-2-222-02070-7. MR 0539936.

[1]

[2]

[3]

[4]

[5]

[6]

[7]