ON PROPERTIES OF GRAPHS

Abstract. This paper looks at three di↵erent graph classes, aiming

to properly define them and find values for their clique, indepen-
dence, and dominating numbers. Two of these graphs, the windmill
Wn and the firecracker Fn,m , are known; the third, the spiderweb
Sn,m , is a graph of our own creation. We show that the windmill,
firecracker, and spiderweb graphs have clique numbers of 3, 2, and
3; independence numbers of n, d n 2
e + n(m 1), and either 2b m 2
c
or 1 + b m2
c (depending on the values of n and m; and dominating
numbers of 1, n, and n + dme, respectively. We conclude that finding
these values is helpful in deepening our understanding of how these
graphs behave.

1. Introduction
In this paper, we will examine three di↵erent types of graphs and various
properties associated with them. The first graph we will look at is called
the windmill graph, denoted Wn , which produces a windmill shape with
n “fan blades.” Next, we will discuss the firecracker graph, denoted Fn,m ,
which resembles a lit firecracker. Finally, we will introduce a graph of our
own design, which we have named the spiderweb graph, or Sn,m . As the
name suggests, this graph is meant to resemble a spiderweb. Precise defi-
nitions for the vertex and edge sets of these three graphs can be found in
the Background and Definitions section.

For each of these three graph classes, we will define their order (number
of vertices), size (number of edges), and minimum and maximum degree
(the smallest and and largest number of edges, respectively, that any ver-
tex can be connected to). We also aim to show through proof values for
these graphs’ clique numbers (corresponding to the largest possible com-
plete subgraph), independence numbers (corresponding to the largest pos-
sible empty subgraph), and dominating numbers (the smallest number of
vertices needed to reach every point on the graph through connected edges).

Date: December 13, 2021.

1
 2. Background and Definitions
In this section we define the three graphs’ vertex and edge sets; provide
visuals for each graph; and determine their order, size, and minimum and
maximum degree.
2.1. Windmill graph Wn . As mentioned in the Introduction section, a
windmill graph creates a fan shape with n triangular “fan blades.”[3] An
example with four blades, or a W4 graph, is shown in Figure 1.

Figure 1. A windmill graph with four “blades,” or a W4 .

The windmill graph’s vertex set V (Wn ) and edge set E(Wn ) are defined as
follows:
V (Wn ) = {v0 , v1 , v2 , . . . , v2n } and
E(Wn ) = {{v0 , v2i+1 , v2i+2 } : 0  i  n 1}.
The vertex v0 acts as the center of the windmill and connects to every
other point on the graph. The non-center points are arranged in pairs and
connected to each other and the center in triangles, which create the “fan
blade” shapes. As we can see from the edge set, the order of this graph is
|V | = 2n + 1,
accounting for all the pairs of points on the blades plus the center point.
Since each of these n fan blades creates a three-edge triangle, we can also
say that the graph’s size is
|E| = 3n.
page 2 of 10
 On Properties of Graphs
The maximum degree of the windmill is 2n, held by the center point v0 ,
since this point is connected to all other points on the graph. Points v1
through v2n are only connected to two other points each, giving the graph
a minimum degree of 2.
2.2. Firecracker graph Fn,m . In order to produce its namesake shape,
the firecracker graph consists of a path n vertices long, with each vertex
connected to a distinct m-point star subgraph[3]. Figure 2 shows a picture
of an F5,5 graph, with a 5-vertex path and 5-point stars.

Figure 2. A firecracker graph consisting of a 5-vertex

path and 5-point stars, or an F5,5 .

For convenience’s sake, we can break up the firecracker graph’s vertex set
into three separate subsets:
V1 (Fn,m ) = {v1 , v2 , . . . , vn },
V2 (Fn,m ) = {vn+1 , vn+2 , . . . , v2n }, and
V3 (Fn,m ) = {u1 , u2 , . . . , un(m 1) }.

Here, V1 creates the base path of n vertices, V2 creates the center points of
the n star subgraphs, and V3 creates the m 1 points (not connected to
the base path) for each of the n star subgraphs. We can divide the edge
set up similarly:
E1 (Fn,m ) = {{vi , vi+1 } : 1  i  n 1},
E2 (Fn,m ) = {{vi , vn+i : 1  i  n}, and
E3 (Fn,m ) = {{vn+i , uj } : 1  i  n, 1  j  m 1}.
The first set E1 gives us the base path with vertices v1 through vn , the next
set E2 connects each point on the path with the center point of a star, and
finally the set E3 connects these center star points to the other points in
their respective stars.

Considering that the firecracker graph has n points on its base path and m
more points for each of the n stars, we can see that its order is
|V | = n + nm.
page 3 of 10
We also know that an n-vertex-long path has n 1 edges, and that an
m-pointed star graph has m edges. Combining these two pieces, it becomes
apparent that the firecracker graph has

|E| = (n 1) + nm

for its size. Interestingly, this value is just 1 less than the graph’s order.

The minimum and maximum degree of the firecracker graph primarily de-
pend on the value of m. If m = 1, each point on the star is only connected
via one other edge, so the minimum degree becomes 1. However, if m 2,
the endpoints of the base path hold the minimum degree, which is 2. In
similar fashion, the maximum degree of the graph is m, the number of rays
on each star, so long as m 3. But if m < 3, the maximum degree becomes
the degree of any of the non-endpoint path vertices, which is 3.

2.3. Spiderweb graph Sn,m . Our spiderweb graph is composed of a cen-

ter point, an inner cycle of n points each connected to the center, and an
outer cycle of m points such that each point on the n-cycle is connected
to an equal number of points on the m-cycle. For this to be the case, we
establish the condition on Sn,m that n | m. We also specify that n 3 to
give us sufficiently large inner and outer cycles. An example of a spiderweb
graph – specifically, an S4,8 with four vertices on the inner cycle and eight
on the outer cycle – is included in Figure 3.

Figure 3. A spiderweb graph with a 4-point inner cycle

and an 8-point outer cycle, denoted S4,8 .
page 4 of 10
 On Properties of Graphs
We have two subsets that make up the vertex set of Sn,m :
V1 (Sn,m ) = {v0 , v1 , v2 , . . . , vn } and
V2 (Sn,m ) = {u1 , u2 , . . . , um }.
The first set includes both the center point v0 and all the inner cycle points
v1 through vn ; the second set includes all the outer cycle points u1 through
um .

The edge set is a little trickier. We will split it up into four subsets as
follows:
E1 (Sn,m ) = {{v0 , vi } : 1  i  n},
E2 (Sn,m ) = {{vi , vi+1 } : 1  i  n 1} [ {v1 , vn },
E3 (Sn,m ) = {{u1 , ui } : 1  i  m} [ {u1 , um }, and
m m
E4 (Sn,m ) = {{vi , uj } : 1  i  n, (i 1)  j  i}.
n n
Here, E1 connects the center point to every vertex on the inner cycle, and
E2 and E3 build the inner and outer cycles, respectively. Lastly, E4 con-
nects every point on the inner cycle to an equal number of points on the
outer cycle, depending on the number of vertices in each cycle. The number
of edges between a vertex on the inner cycle and some vertices on the outer
cycle is dependent on the ratio of outer points to inner points, or m
n.

The order of this spiderweb graph is fairly straightforward to obtain. If we

add together the center vertex, the n inner cycle vertices, and the m outer
cycle vertices, we get
|V | = 1 + n + m.
For the size, we must consider the n edges from the center to the inner
cycle, the n more edges from the inner cycle itself, the m edges from the
outer cycle, and the m more edges connecting the two cycles. Adding these
up gives us
|E| = n + n + m + m = 2n + 2m
for the graph’s size.

Since 3  n  m, each vertex on the spiderweb graph will be connected

to at least three other points, yielding a minimum degree of 3. This is
especially apparent when m > n, as each point on the m-cycle will only
connect to three more points regardless of the size of n or m. For small
graphs, the maximum degree can come from the center, which has degree
n. For larger graphs, however, the maximum value comes from the points
on the inner cycle, which each connect to the center, two other points on
page 5 of 10
 m
the n-cycle, and n points on the m-cycle. We say, then, that the maximum
degree is
m
(Sn,m ) = max{n, + 3}.
n
3. Results
In this section, we will focus on the clique, independence, and dominating
numbers of the three di↵erent graphs, and attempt to show or prove their
respective values.
3.1. Windmill graph results. Since the windmill graph is made up of
distinct 3-cycles, or groups of three vertices connected to each other by two
edges apiece, it is easy to see that the graph’s clique number is at least 3.
In Theorem 3.1, we prove that it is exactly 3.
Theorem 3.1. The clique number of a Windmill graph is given by
!(Wn ) = 3.
Proof. We begin by observing how every Wn has a clique number of at least
3. As mentioned above, a C3 (a three-vertex cycle graph) is isomorphic to
a K3 , and since a windmill graph is made up of n C3 ’s, each of those is a
K3 and thus is a clique of three vertices[2].

A higher clique number – say, 4 – would require at least four vertices all
joined to each other with edges; that is, four vertices with degree 3. How-
ever, the only vertex with a degree higher than 2 is v0 , so this is impossible.
Therefore, the clique number of a windmill graph is exactly 3.
The center vertex cannot be included in the independence number, since
it connects to all other points on the graph. Therefore, we must use the
outer “fan blade” vertices to create as large an empty subgraph as possible.
We can take one point from each of the n blades to form a set in which no
vertices are connected. With this, we can say that
↵(Wn ) = n.
Finally, the windmill’s dominating number is trivial; since the center vertex
connects to every other vertex on the graph, we can say that
(Wn ) = 1.
A property often used in chemistry (discussed in topology) is the Weiner
Index of a graph, denoted W (G), which is the total distance between every
vertex taken by the shortest path between them.[1] The first few Weiner
Indices of a Windmill graph are as follows:
W (W1 ) = 3, W (W2 ) = 14, W (W3 ) = 33, W (W4 ) = 60.
page 6 of 10
 On Properties of Graphs
This sequence is in fact in the OEIS as A033991. [4]
3.2. Firecracker graph results. Like the windmill graph, finding the
clique number of the firecracker graph is fairly simple. Since the graph
includes a path subgraph, we know the clique number must be at least 2.
However, because only one point on the path connects to each star, and
because none of the stars connect to each other, we can see that a clique
number of 3 or higher is impossible to achieve. Therefore,
!(Fn,m ) = 2.
The dominating number is not quite as straightforward, but still relatively
simple. We can think of firecracker graphs as n star graphs (where the
center vertex is connected to all other vertices) of size m who all have
one outer vertex connected via a path. Similar to the windmill graph, the
dominating number for star graphs is 1. So, we can think of n disjoint star
graphs as having a dominating number of n. The fact that there is a path
connecting these stars does not lower the dominating number, since we still
need to use each star’s center for the dominating set. Therefore,
(Fn,m ) = n.
We now arrive at our first complex property for firecracker graphs:
Theorem 3.2. The independence number of a firecracker graph is given by
n
↵(Fn,m ) = d e + n(m 1).
2
Proof. First, let us observe the independence set that results in the claimed
independence number. Once again, we note that a firecracker graph is es-
sentially a combination of a star graph with a path connecting each star.
We know that the independence set of a path is every other vertex, so a
Pn has an independence number of d n2 e[3]. We now observe that the in-
dependence set of a star graph is every vertex besides the center vertex,
so with n star graphs, the independence number is n(m). However, one of
those outside vertices is part of the path, which we have already accounted
for. Therefore, as to not double count, the independence number of the
star graphs is n(m 1). So, adding these together yields the independence
number claimed in Theorem 3.2.

In order to show the independence number cannot be any larger, we must

verify that none of the remaining vertices not in the independence set can be
in the independence set. The two types of vertices not in the independence
set are the center vertices of each induced Sm and every other vertex in
the induced Pn , as can be seen by the red vertices in the example F5,4 in
Figure 4. We recognize that all of these vertices are adjacent to vertices in
the independence set so cannot be added to it. We have therefore proven
page 7 of 10
that the independence set cannot be any larger than d n2 e + n(m 1), and
since we know there is an independence set that satisfies that number, the
independence number is as given.

Figure 4. F5,4 The independence set of a F5,5 , shown by

the green vertices.

3.3. Spiderweb graph results. The spiderweb graph undoubtedly has

the most complex properties of our three classes. We begin with the sim-
plest property: the clique number. There are various K3 subgraphs in a
spiderweb, such as the subgraph induced by the center vertex and two of its
adjacent vertices; for example, see v0 , v1 , andv2 in Figure 3. There cannot
be a K4 subgraph. The easiest way to see this is by noting that the center
vertex will never be adjacent to a vertex on the outer level. Therefore,
!(Sn,m ) = 3.
We continue by analyzing the dominating number of an Sn,m graph. There
are a few ways to select the dominating set, but many of those ways are
only the most efficient for some intervals of m
n . Theorem 3.3 outlines the
most efficient way to select the dominating set for any Sn,m .
Theorem 3.3. The dominating number of an Sn,m graph is given by
m
(Sn,m ) = 1 + d e.
3
Proof. We first observe the dominating set that satisfies the theorem. We
notice that the first two layers of an Sn,m – that is, the center point and
inner cycle – induce a star graph with n leaves. So, we can dominate the
first two layers by assigning the center vertex to be in the dominating set.
All that remains is the outermost layer, which induces a cycle of size Cm .
We know that the dominating number of a cycle Cm is d m 3 e[3], with every
third vertex in the dominating set, along with one of the remaining vertices
in the cycle if n - 3[3]. Figure 5 shows an example of choosing the domi-
nating set in this manner.

In order to prove the dominating number cannot be any smaller, we verify

that every vertex in the dominating set is necessary to cover the entire
graph. It is clear that removing the center vertex would cause the center
vertex to not be dominated, as well as a few vertices in the second layer.
page 8 of 10
 On Properties of Graphs
We also cannot remove any of the vertices on the outer layer as they will no
longer be dominated, along with a few of the vertices they were dominating.
As a result, every vertex in the dominating set is necessary, and therefore
this configuration of dominating vertices is the most efficient, resulting in
the dominating number to be 1 + d m 3 e.

Figure 5. S5,10 The dominating set of an S5,10 graph,

shown by the green vertices.

The independence number of a spider graph is certainly the most complex

graph property in this paper; therefore, fittingly, it has been saved for last.
The independence number is a piecewise function, as the set that yields the
desired independence number is di↵erent depending on whether n = m or
if n < m.
Theorem 3.4. The independence number of an Sn,m graph is given by
(
2 · b n2 c, n=m
↵(Sn,m ) =
1 + bm 2 c, n < m.
Proof. We begin by showing the independence set that satisfies each case
of the given theorem. First, let us look at the case where n = m. We know
that the independence number of a Cn graph is b n2 c. So, we choose every
other vertex on the inner layer of the Sn,m graph. Since n = m, we will
also choose every other vertex on the outer layer, but starting one o↵ from
the every other on the inner layer.

Moving on to when n < m, we notice that the middle vertex and every
other vertex in the outer layer are all disjoint, and satisfy the prescribed
value above for the independence number of any spiderweb graph. We know
that this has to be the floor of m
2 , since the outer layer is an induced Cm ,
and the independence number for a Cm is b m 2 c.

page 9 of 10
We now prove that the independence set cannot be any larger for each case.
For the n = m case, we cannot add the center vertex, and every vertex on
the inner and outer layers is adjacent to vertices in the independence set.
For the n < m case, we notice that any vertex in the inner layer cannot be
added to the independence set since they are adjacent to the middle vertex.
Similarly, on the outer layer, every vertex not in the independence set is
adjacent to a vertex in the independence set. We continue by establishing
why each case is the most efficient. When n = m, we notice by the nature
of the graph that n, m 3. So, 2 · b n2 c 1 + b n2 c.

On the other hand, when n < m, this means m 2n by the definition of

an Sn,m . So, for all n < m, 2 · b n2 c  1 + b m
2 c. Therefore, each case yields
the most efficient independence set for its respective spiderweb graph.
We conclude by observing a shared property of all the graph classes we
have analyzed. Kuratowski’s Theorem states that a graph is planar if and
only if it contains no subspace homeomorphic to K3,3 or K5 . [1] However,
a more simple definition of planar is that it can be drawn on a piece of
paper without any crossings. Coincidentally, all of the graph families we
have analyzed do not contain any crossings in the ways we have chosen to
draw them, so they are all planar graphs.

4. Conclusion
As shown in the Results section, we were able to find values for the clique,
independence, and dominating numbers of all three graph classes, either as
constants or as functions of n and m. These values are helpful for telling us
the largest possible complete and empty subgraphs we can find within them,
along with the lowest number of vertices needed to reach every vertex with
an edge. This in turn can lead to the discovery of more useful properties,
such as whether or not the graphs are planar. Overall, we accomplished
our goal of exploring how the windmill, firecracker, and spiderweb graphs
are constructed and how they behave as a result.

References
1. Colin Adams and Robert Franzosa, Introduction to topology, Pearson Education Inc.,
2008.
2. Edward R. Scheinerman, Mathematics: A discrete introduction, Cengage Learning,
2013.
3. Nathan Shank, private communication, 2021.
4. N. J. A Sloane, A033991.

page 10 of 10