In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
field of
graph theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, the windmill graph is an
undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
constructed for and by joining copies of the
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices ...
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
In graph theory, a branch of combinatorial mathematics, a block graph or clique tree.
is a type of undirected graph in which every biconnected component (block) is a clique.
Block graphs are sometimes erroneously called Husimi trees (after ...
.
Special cases
By construction, the windmill graph is the
friendship graph , the windmill graph is the
star graph
In graph theory, a star is the complete bipartite graph a tree (graph theory), tree with one internal node and leaves (but no internal nodes and leaves when ). Alternatively, some authors define to be the tree of order (graph theory), order ...
and the windmill graph is the
butterfly graph.
Labeling and colouring
The windmill graph has
chromatic number
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
and
chromatic index
In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...
. Its
chromatic polynomial
The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to stu ...
can be deduced form the chromatic polynomial of the complete graph and is equal to
:
The windmill graph is proved not
graceful
Gracefulness, or being graceful, is the physical characteristic of displaying "pretty agility", in the form of elegant movement, poise, or balance. The etymological root of ''grace'' is the Latin word ''gratia'' from ''gratus'', meaning pleasing ...
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
References
{{reflist
Parametric families of graphs
Perfect graphs