Windmill graph
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In the mathematical field of graph theory, the windmill graph is an undirected graph constructed for and by joining copies of the complete graph at a shared universal vertex. That is, it is a 1-clique-sum of these complete graphs.
In the mathematical field of graph theory, the windmill graph is an undirected graph constructed for and by joining copies of the complete graph at a shared universal vertex. That is, it is a 1-clique-sum of these complete graphs. ==Properties== It has vertices and edges, girth 3 (if ), 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 -edge-connected. It is trivially perfect and a block graph. ==Special cases== By construction, the windmill graph is the friendship graph , the windmill graph is the star graph and the windmill graph is the butterfly graph. ==Labeling and colouring== The windmill graph has chromatic number and chromatic index . 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 is proved not graceful if . In 1979, Bermond has conjectured that is graceful for all . Through an equivalence with perfect difference families, this has been proved for . Bermond, Kotzig, and Turgeon proved that is not graceful when and or , and when and . The windmill is graceful if and only if or . ==Gallery==
Text derived from https://en.wikipedia.org/w/index.php?oldid=1326505607 under CC BY-SA 4.0; modifications have been made.