A graph G(V, E) is Γ-harmonious when there is an injection f from V to an Abelian group Γ such that the induced edge labels defined as w(xy) = f(x) + f(y) form a bijection from E to Γ. We study Γ-harmonious labelings of several cycles-related classes of graphs, including Dutch windmills, generalized prisms, generalized closed and open webs, and superwheels.
Harmonious graphs have been extensively studied since 1980, when Graham and Sloane [1]first defined the notion.
A graph
That is, the induced function
In this paper, we study the concept of
We will present several classes of cycles-related graphs that are
We will use
First we repeat the formal definition of
Definition 1. Let
When
Definition 2. A graph
Now we present definitions of the classes of graphs studied in the following sections.
Definition 3. The wheel graph
The wheel graph is often described as
Definition 4. The superwheel
The number of edges in
Definition 5. The Dutch windmill graph
The number of edges of
Definition 6. The generalized prism
The number of edges in
Definition 7. The generalized closed
web
The number of edges in
Definition 8. The generalized open web
The number of edges in
For the sake of completeness, we first state some well known group theory results, which we will use later, starting with The Fundamental Theorem of Finite Abelian Groups. Although the reader is probably familiar with the theorems, we include them primarily because of introducing notation that will be used throughout the paper.
Theorem 1 (The Fundamental Theorem of Finite Abelian
Groups). Let
Then
Sometimes it is useful to express an Abelian group in a different way.
Theorem 2. Let
Another well known theorem is the following.
Theorem 3. An Abelian group
The following observation will be useful.
Observation 4. Let
Proof. Let
For the same reason as above we must have
Another well-known result will be useful.
Theorem 5. Let
if
if
The main building block we will be using in our constructions is a theorem that follows as a direct corollary form a group theory result proved by Beals, Gallian, Headly and Jungreis [4]. They studied harmonious groups.
Definition 9. A finite group
They proved the following characterization of harmonious groups.
Theorem 6 (Beals et al. [4]). If
In other words, all non-trivial Abelian groups of odd order are
harmonious, and a harmonious group of even order must contain a
subgroup isomorphic to
An immediate consequence of Theorem 6 is a
result on
The first result on cycle-related harmonious graphs was proved by
Graham and Sloane [1]. Note that “harmonious” here means
“
Theorem 7 (Graham and Sloane [1]). The cycle
A more general theorem is a direct consequence of Theorem 6. Although it is technically speaking a new result, as it was not formally stated and proved in [4], we state it here because we believe that the authors were aware of it.
Theorem 8. The cycle
Proof. This follows directly from Theorem 6. Label the vertices consecutively
with the elements of
Graham and Sloane [1]further proved the following result on wheel graphs.
Theorem 9 (Graham and Sloane [1]). All wheels
We generalize their result in the Section 7. We prove
that odd wheels
Gallian [5]cites [6]which has the following two results on superwheel graphs.
Theorem 10 (Gnanajothi [6]). The superwheel
graph
Theorem 11 (Gnanajothi [6]). The superwheel
graph
We will show that all odd superwheel graphs are strongly
Graham and Sloane [1] also established the following result on Dutch windmill graphs.
Theorem 12 (Graham and Sloane [1]). The Dutch windmill graph
We will prove that when both
Also, Graham and Sloane [1]proved the following result on generalized prisms.
Theorem 13 (Graham and Sloane [1]). The generalized prism
Later, Gallian, Prout and Winters [7]showed the following result on even prisms.
Theorem 14 (Gallian et al. [7]). The prism
Jungreis and Reid [8]showed the following results on type
harmonious prisms.
Theorem 15 (Jungreis and Reid [8]). The generalized prism
We prove results on generalized prisms showing
Seoud and Youssef [9]proved the following two results on
open webs (or helm graphs)
Theorem 16 (Seoud and Youssef [9]). The open web
Theorem 17 (Seoud and Youssef [9]). The closed web
In [5], Gallian
cites [6]which
states the following result on open webs
Theorem 18 (Gnanajothi [6]). The open web
We will generalize results on
The superwheel
Theorem 19. The superwheel
Proof. Let
Assume
Since for a fixed
We illustrate the method by two examples.
Example 1. A
Example 2. A
The Dutch windmill graph
We know that
Before we start constructing the vertex labeling of
Observation 20. If
Proof. Since
Let
Let us look at a specific example how we would use this lemma to
construct a vertex labeling of
Example 3.
Here, we have,
In Figure 3(b),
Theorem 21. When
Proof. We will use Observation 20 to construct a vertex
labeling
We start by labeling the central vertex
First we want to show that this construction produces a well-defined
vertex labeling. Suppose that for some
and
and we have a contradiction, because in Observation 20 we have shown that
Second, we must check if this construction induces a
In
For a fixed
Now suppose that for a fixed
Finally suppose for
Then
for some
When
Theorem 22. For
Proof. Let
When
For generalized prisms, our result is again more general for
Recall that the number of edges of the generalized prism
We illustrate the method in two examples.
Example 4. We present a labeling of
Example 5. We present a labeling of
Theorem 23. Let
Proof. We will use the following notation. Each
Let
Hence there exists an
Because
For paths, the label of
Because we have
For convenience, we express the above result in more explicit form,
describing the group
Corollary 1. Let
Proof. By Theorem 5 part 2, there
exists a subgroup
Corollary 2. Let
then the prism
Proof. By Observation 4,
When
When
For computation convenience, we slightly change the notation here and
number the cycles of the generalized prism
A generalized closed web is then a graph arising from
The number of edges and order of
Theorem 24. Let
Proof. We will use the following notation. The central
vertex of degree
The number of edges in
By our assumption,
Notice that in the cycle
For paths, the label of
For the remaining path edges, the set of labels between cycles
We obtained
Example 6. A
Example 7. A
Recall that Seoud and Youssef [9]proved that closed webs
Corollary 3. The closed web
We again express the previous result of Theorem 24 in terms of the nested form of
Corollary 4. Let
Proof. Similarly as in the proof of Corollary 1, this follows from Theorems 6, 8, and 24.
For even
Corollary 5. Let
then the closed web
Proof. We again denote
In Case (1), because
In Case (2), because
In Case (3), because
Finally, in Case (4),
Therefore, the proof again follows from Theorems 6, 8 and 24.
A generalized open web
The proof of the following theorem is just a slight modification of the proof of Theorem 24 and is left to the reader.
Theorem 25. Let
Example 8. A
Example 9. A
Seoud and Youssef [9]and Gnanajothi [6]proved that open webs
Corollary 6. The open web
For convenience, we again express the result of Theorem 25 in a more explicit form, describing
the group
Corollary 7. Let
Proof. This follows directly from Theorems 6, 8 and 25.
Corollary 8. Let
then the web
The proofs are identical to the proofs of Corollaries 1 and 2, respectively.
We explored
There are two main directions for further research. One is dealing
with graphs based on even cycles where the group
Problem 1. Determine for what Abelian groups
For Dutch windmill graphs, we only covered the cases when the number of cycles is odd. When the cycle length was even, we have an additional restriction on the quotient group. We propose the following two problems on Dutch windmill graphs.
Problem 2. Determine for what Abelian groups
Problem 3. Determine for what Abelian groups
The other direction concerns graphs
Problem 4. Determine for what Abelian groups
of order
of order
We also want to express out thanks to Alexa Hedtke and Johnathan Koch
for their contribution to our results in the early stages of this
project. Johnathan Koch wrote a program in python which we used to check
if a
1970-2025 CP (Manitoba, Canada) unless otherwise stated.