windmill graph
{{short description|Graph family made by joining complete graphs at a universal node}}
{{infobox graph
| name = Windmill graph
| image = 220px
| image_caption = The Windmill graph {{math|Wd(5,4)}}.
| vertices = {{math|n(k − 1) + 1}}
| edges = {{math|{{sfrac|nk(k − 1)|2}}}}
| automorphisms =
| girth = 3 if {{math|k > 2}}
| diameter = 2
| radius = 1
| chromatic_number = {{mvar|k}}
| chromatic_index = {{math|n(k − 1)}}
|notation = {{math|Wd(k,n)}}
| properties =
}}
In the mathematical field of graph theory, the windmill graph {{math|Wd(k,n)}} is an undirected graph constructed for {{math|k ≥ 2}} and {{math|n ≥ 2}} by joining {{mvar|n}} copies of the complete graph {{mvar|K{{sub|k}}}} at a shared universal vertex. That is, it is a 1-clique-sum of these complete graphs.{{cite journal |last=Gallian |first=J. A. | author-link = Joseph Gallian |title=A dynamic survey of graph labeling |journal=Electronic Journal of Combinatorics |volume=DS6 |pages=1–58 |date=3 January 2007 |url=http://www.combinatorics.org/Surveys/ds6.pdf|mr=1668059 }}
Properties
It has {{math|n(k − 1) + 1}} vertices and {{math|nk(k − 1)/2}} edges,{{MathWorld|urlname=WindmillGraph|title=Windmill Graph}} girth 3 (if {{math|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 {{math|(k − 1)}}-edge-connected. It is trivially perfect and a block graph.
Special cases
By construction, the windmill graph {{math|Wd(3,n)}} is the friendship graph {{mvar|F{{sub|n}}}}, the windmill graph {{math|Wd(2,n)}} is the star graph {{mvar|S{{sub|n}}}} and the windmill graph {{math|Wd(3,2)}} is the butterfly graph.
Labeling and colouring
The windmill graph has chromatic number {{mvar|k}} and chromatic index {{math|n(k − 1)}}. Its chromatic polynomial can be deduced from the chromatic polynomial of the complete graph and is equal to
:
The windmill graph {{math|Wd(k,n)}} is proved not graceful if {{math|k > 5}}.{{cite journal |first1=K. M. |last1=Koh |first2=D. G. |last2=Rogers |first3=H. K. |last3=Teo |first4=K. Y. |last4=Yap |title=Graceful graphs: some further results and problems |journal= Congressus Numerantium |volume=29 |pages=559–571 |year=1980 |mr=0608456}} In 1979, Bermond has conjectured that {{math|Wd(4,n)}} is graceful for all {{math|n ≥ 4}}.{{cite book |first=J.-C. |last=Bermond |chapter=Graceful graphs, radio antennae and French windmills |editor-first=Robin J. |editor-last=Wilson |editor-link=Robin Wilson (mathematician) |title= Graph theory and combinatorics (Proc. Conf., Open Univ., Milton Keynes, 1978) |chapter-url=https://books.google.com/books?id=7-_uAAAAMAAJ |year=1979 |publisher=Pitman |pages=18–37 |series=Research notes in mathematics | volume=34 |isbn=978-0273084358 |oclc=757210583|mr=0587620}} Through an equivalence with perfect difference families, this has been proved for {{math|n ≤ 1000}}.
Bermond, Kotzig, and Turgeon proved that {{math|Wd(k,n)}} is not graceful when {{math|1=k = 4}} and {{math|1=n = 2}} or {{math|1=n = 3}}, and when {{math|1=k = 5}} and {{math|1=n = 2}}.{{cite book |first1=J.-C. |last1=Bermond |first2=A. |last2=Kotzig|author2-link= Anton Kotzig |first3=J. |last3=Turgeon |chapter=On a combinatorial problem of antennas in radioastronomy |editor-first=A. |editor-last=Hajnal |editor2-first=Vera T. |editor2-last=Sos |title=Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I |chapter-url=https://books.google.com/books?id=OPtUvQEACAAJ |year=1978 |publisher=North-Holland |volume=18 |series=Colloquia mathematica Societatis János Bolyai |isbn=978-0-444-85095-9 |pages=135–149 |mr=0519261}} The windmill {{math|Wd(3,n)}} is graceful if and only if {{math|n ≡ 0 (mod 4)}} or {{math|n ≡ 1 (mod 4)}}.{{cite book |first1=J.-C. |last1=Bermond |first2=A. E. |last2=Brouwer |author2-link= Andries Brouwer |first3=A. |last3=Germa |chapter=Systèmes de triplets et différences associées |title= Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) |chapter-url=https://books.google.com/books?id=0u3uAAAAMAAJ |year=1978 |publisher=Éditions du Centre national de la recherche scientifique |isbn=978-2-222-02070-7 |volume=260 |series=Colloques internationaux du Centre National de la Recherche Scientifique |pages=35–38|mr=0539936}}
