On Some Classes of Cycles-Related Γ-Harmonious Graphs

Gyaneshwar Agrahari1, Dalibor Froncek2
1Louisiana State University, Baton Rouge, Louisiana
2University of Minnesota Duluth, United States

Abstract

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.

Keywords: Harmonious labeling, Abelian group

1. Introduction

Harmonious graphs have been extensively studied since 1980, when Graham and Sloane [1]first defined the notion.

A graph G=(V,E) with q edges is harmonious if there exists an injection f from the set of vertices of G to the additive group Zq, f:VZq such that the induced edge labels w(e) of all edges, defined as w(xy)=(f(x)+f(y))modq, are all distinct.

That is, the induced function w:EZq is a bijection. When G is a tree, exactly one vertex label is repeated. Graham and Sloane proved that almost all graphs are not harmonious. They also proved that if a harmonious graph has an even number of edges q and the degree of every vertex is divisible by 2k then q is divisible by 2k+1. Liu and Zhang [2]generalized this condition and also proved that there is no forbidden subgraph condition for harmonious graphs, that is, that every graph is a subgraph of a harmonious graph.

In this paper, we study the concept of Γ-harmonious graphs by extending the notion of harmonious graphs to any Abelian group Γ. We say that a graph G with q edges is Γ-harmonious for a given Abelian group Γ of order q if there exists an injection f:VΓ such that the induced labels w(e) of all edges, defined as w(xy)=f(x)+f(y) (where the addition is performed in Γ), are again all distinct. In other words, the induced function w:EΓ is a bijection. This notion was introduced by Montgomery, Pokrovskiy and Sudakov in [3], but their results were all dealing just with cyclic groups. We are not aware of any results for non-cyclic groups whatsoever.

We will present several classes of cycles-related graphs that are Γ-harmonious for various Abelian groups Γ. All groups in this paper are finite.

2. Definitions and Notation

We will use A,H for subgroups, and the group operation will be the usual component-wise addition. A coset determined by a subgroup A of Γ and a coset representative α will then be denoted by α+A. A cyclic subgroup of Zn generated by an element a will be denoted by an or simply a if no confusion can arise.

First we repeat the formal definition of Γ-harmonious graphs.

Definition 1. Let G=(V,E) be a graph with q edges and Γ an Abelian group of order q. We say that G is Γ-harmonious if there exists an injection f:VΓ (called Γ-harmonious labeling) with the property that the induced labels w(e) of all edges, defined as w(xy)=f(x)+f(y) (where the addition is performed in Γ), are all distinct. In other words, the induced function w:EΓ is a bijection.

When Γ=Zq, then a Zq-harmonious graph is simply called harmonious.

Definition 2. A graph G with q edges is strongly Γ-harmonious if it is Γ-harmonious for all Abelian groups of order q.

Now we present definitions of the classes of graphs studied in the following sections.

Definition 3. The wheel graph Wn arises from the cycle Cn by adding a single vertex and joining it by an edge to every vertex of the cycle.

The wheel graph is often described as Cn+K1.

Definition 4. The superwheel SWk,n is a graph arising from the cycle Cn by adding k vertices not adjacent to each other but adjacent to every vertex in Cn.

The number of edges in SWk,n is (k+1)n. It can be also described as Cn+kK1 or Cn+Kk¯. When k=1, SW1,n is just the wheel Wn.

Definition 5. The Dutch windmill graph Dnm is a graph consisting of m copies of Cn with a common vertex, called the central vertex. The n-cycles in Dnm are also called blades.

The number of edges of Dnm is nm. When m=1, Dn1 is a cycle; thus, in our examination, m>1. For n=3, the graph D3m is also called the friendship graph.

Definition 6. The generalized prism Ym,n is the Cartesian product of the path Pm and the cycle Cn.

The number of edges in Ym,n is (2m1)n. When m=2, we obtain the usual prism. The cycle Cn can also be seen as the degenerate generalized prism Y1,n.

Definition 7. The generalized closed web CWm,n is a graph arising from the generalized prism Ym,n by adding a new vertex and joining it by an edge to every vertex of degree three of the top cycle of Ym,n.

The number of edges in CWm,n is 2mn. The closed web CW2,n is sometimes also called the closed helm (see below). The wheel Wn is CW1,n.

Definition 8. The generalized open web OWm,n is a graph arising from the generalized closed web CWm,n by removing the edges of the bottom cycle Cn.

The number of edges in OWm,n is (2m1)n. The generalized open web OWm,n is sometimes called just the generalized web. The open web OW2,n is better known as the helm graph. The usual web graph is then OW3,n.

3. Harmonious Groups

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 Γ be an Abelian group of order n=p1s1p2s2pksk, where k1, p1,p2,,pk are primes, not necessarily distinct, and s1,s2,,sk positive integers.

Then Γ is isomorphic to Zp1s1Zp2s2Zpksk and if we moreover require that for every i=1,2,,k1 we have pipi+1 and if pi=pi+1, then sisi+1, then the expression determined by the k-tuple (p1s1,p2s2,,pksk) is unique and we call it the canonical form of the group Γ.

Sometimes it is useful to express an Abelian group in a different way.

Theorem 2. Let Γ=Zp1s1Zp2s2Zpksk of order n be as in Theorem 1. Then it can be written in a unique way in nested form as Γ=Zn1Zn2Znt, where nt2, n=n1n2nt, and ni+1ni for i=1,2,,t1.

Another well known theorem is the following.

Theorem 3. An Abelian group Γ=Zp1s1Zp2s2Zpksk is cyclic if and only if all primes pi, i=1,2,,k are distinct.

The following observation will be useful.

Observation 4. Let Γ=Zn1Zn2Znt of order n satisfy conclusion of Theorem 2 and H be its cyclic subgroup of order m. Then mn1 and Zn1 has a cyclic subgroup of order m.

Proof. Let Zq1z1Zq2z2Zqrzr be the canonical form of Zn1. Then by Theorem 3 q1,q2,,qr are all distinct. Moreover, q1,q2,,qr are all primes in the multiset {p1,p2,,pk} defining the canonical form of Γ. For if not, then there is pi which appears in the canonical form of some Znj,j>1 but not in {q1,q2,,qr}. But then nj does not divide n1, which contradicts Theorem 2. Therefore, we can write H as Zq1u1Zq2u2Zqrur, where we allow each ui to be a non-negative integer.

For the same reason as above we must have uizi for every i=1,2,,r, since otherwise qiui appears in the canonical form of some Znj,j>1 and njn1, a contradiction. ◻

Another well-known result will be useful.

Theorem 5. Let Γ be a finite Abelian group. Then

  • if H is a subgroup of Γ, then the quotient group Γ/H is isomorphic to some subgroup K of Γ, and conversely,

  • if K is a subgroup of Γ, then there exists a subgroup H such that KH={e} and the quotient group Γ/H is isomorphic to K.

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 Γ of order n is harmonious if the elements can be ordered (g1,g2,,gn) so that the set of element products {g1g2,g2g3,,gn1gn,gng1} is equal to the set of all elements of Γ. The ordered list (g1,g2,,gn) is called the harmonious sequence of Γ.

They proved the following characterization of harmonious groups.

Theorem 6 (Beals et al. [4]). If Γ is a finite, non-trivial Abelian group, then Γ is harmonious if and only Γ has a non-cyclic or trivial Sylow 2-subgroup and Γ is not an elementary 2-group.

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 Z2Z2 but cannot be equal to Z2Z2Z2. That is, it must contain a subgroup isomorphic to Z2Z2s where s2.

An immediate consequence of Theorem 6 is a result on Γ-harmonious labeling of cycles, which we state in the next section.

4. Known Results

The first result on cycle-related harmonious graphs was proved by Graham and Sloane [1]. Note that “harmonious” here means “Zn-harmonious.”

Theorem 7 (Graham and Sloane [1]). The cycle Cn with n3 is harmonious if and only if n is odd.

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 Cn is Γ-harmonious if and only if Γ is of order n, and

  1. n is odd, or

  2. n is even and Γ has a subgroup isomorphic to Z2Z2s where s2.

Proof. This follows directly from Theorem 6. Label the vertices consecutively with the elements of Γ in their harmonious sequence order. ◻

Graham and Sloane [1]further proved the following result on wheel graphs.

Theorem 9 (Graham and Sloane [1]). All wheels Wn are harmonious.

We generalize their result in the Section 7. We prove that odd wheels W2k+1 are strongly Γ-harmonious, and even wheels are Γ-harmonious for certain groups Γ.

Gallian [5]cites [6]which has the following two results on superwheel graphs.

Theorem 10 (Gnanajothi [6]). The superwheel graph Sk,n is harmonious if n is odd and k=2.

Theorem 11 (Gnanajothi [6]). The superwheel graph Sk,n is not harmonious if n2,4,6mod8 and k=2.

We will show that all odd superwheel graphs are strongly Γ-harmonious and even superwheel graphs are Γ-harmonious for some groups.

Graham and Sloane [1] also established the following result on Dutch windmill graphs.

Theorem 12 (Graham and Sloane [1]). The Dutch windmill graph D3m is harmonious if and only if m2mod4.

We will prove that when both m and n are odd, Dnm is strongly Γ-harmonious. Moreover, we will show for m odd and n even, Dnm is Γ-harmonious for certain groups.

Also, Graham and Sloane [1]proved the following result on generalized prisms.

Theorem 13 (Graham and Sloane [1]). The generalized prism Ym,n is harmonious whenever n is odd and m2.

Later, Gallian, Prout and Winters [7]showed the following result on even prisms.

Theorem 14 (Gallian et al. [7]). The prism Y2,n is harmonious except when n=4.

Jungreis and Reid  [8]showed the following results on type harmonious prisms. Y2m,4n and Y2m+1,4m

Theorem 15 (Jungreis and Reid [8]). The generalized prism Ym,n is harmonious if:

  1. m=2k and n=4l except when (k,l)=(1,1)

  2. m=2k+1 and n=4l

  3. m=2k and n=4l+2

  4. n=2l+1

We prove results on generalized prisms showing Ym,n is Γ-harmonious for some Γ.

Seoud and Youssef [9]proved the following two results on open webs (or helm graphs) OW2,n and closed webs (or closed helms) CW2,n.

Theorem 16 (Seoud and Youssef [9]). The open web OW2,n is harmonious for all n3.

Theorem 17 (Seoud and Youssef [9]). The closed web CW2,n is harmonious for all odd n3.

In [5], Gallian cites [6]which states the following result on open webs OW3,n.

Theorem 18 (Gnanajothi [6]). The open web OW3,n is harmonious when n is odd and n3.

We will generalize results on OW(m,n) and CW(m,n) by showing that they are Γ-harmonious for certain Γ.

5. Superwheels

The superwheel SWk,n is a graph with a cycle of length Cn and has k vertices not adjacent to each other but all adjacent to every vertex in Cn. The number of edges of SWk,n is n(k+1). When k=1, then SWk,n is the wheel Wn.

Theorem 19. The superwheel SWk,n is Γ-harmonious with Γ of order n(k+1) if there exists a subgroup H of order n that satisfies conditions in Theorem 8.

Proof. Let v1,v2,,vn be the vertices of the Cn in SWk,n and u1,u2,,uk be the the vertices in its center. For 1jk, let Ej={ujvi|viV(Cn)}.

Assume H is a subgroup of order n that satisfies Theorem 8. Then we can find a Γ-harmonious labeling of Cn with H. Let (h1,h2,,hn) be a H-harmonious labeling of Cn, where for 1in,vi is labeled with the element hiH. We can write Γ as the following disjoint union, Γ=Hg1+Hg2+Hgk+H for g1,g2,,gk in GH. For 1jk, label the central vertex uj with gj. Thus, for a fixed j, the edge ujvi in Ej would be labeled with gj+hi, which is an element of gj+H.

Since for a fixed j, each gj+hi is distinct, there would be no repetition among the edge labels of the edges in Ej. Hence, the edges of Cn are labeled with elements of H and the edges of Ej are labeled with those of gj+H. Since the cosets are disjoint, there would be no repetition in the edge labels across all edges of SWk,n Thus, we have our Γ-harmonious labeling of SWk,n◻

We illustrate the method by two examples.

Example 1. A Z10Z2 labeling of the superwheel SW3,5.

Figure 1 Labeling of SW3,5 with Z10Z2

Example 2. A Z4Z2Z4 labeling of the superwheel SW3,8.

Figure 2 Labeling of SW3,5 with Z4Z2z4

6. Windmill Graphs

The Dutch windmill graph Dnm is a graph consisting of m copies of Cn with a common vertex, called the central vertex. The n-cycles in Dnm are also called blades. Therefore, the number of edges of Dnm is nm. When m=1, Dnm is a cycle; thus, in our examination, m>1.

We know that m|Γ|. Therefore, there must be a subgroup H of order m and index n. Because Γ is Abelian, H is normal. Therefore, K=Γ/H is a quotient group. Denote the coset representatives of K by γ0=0,γ1,γ2,,γn1, where 0 is the identity element of Γ (and thus of H as well). Since there are m copies of Cn, we can denote each Cn as Cj where 0jm1. Let u be the central vertex. In each Cj, we denote other vertices by vij for i=1,2,,n1 such that the the edges in Cj are e0j=uv1j,eij=vijvi+1j for i=1,2,,n2, and en1j=vn1ju.

Before we start constructing the vertex labeling of Dnm with Γ, it is convenient to prove the following observation. We will show that there exists a valid labeling of Cj with K. The coset representatives of the elements of K in the vertex labeling of vij in the K-harmonious labeling of Cj will be later used in the construction of a valid labeling of Dnm with Γ.

Observation 20. If n is odd then each Cj has a K-harmonious labeling where u is labeled with H.

Proof. Since K is an Abelian group of order n, there exists a K-harmonious labeling of each Cj. Thus, we can find a K-harmonious labeling g of Cj such that u is labeled with H and vij is labeled with g(vij)=γi+H for γi+HK=Γ/H, where γiH. The induced edge label of edge e is denoted by wg(e). Notice that while we are labeling the cycle with cosets, the labeling is well-defined since they are elements of the group K. Notice that we label the cycles with the cosets; this labeling is well-defined because they are elements of K, which is a group.

 Let γ~0+H=γ1+H and γ~n1+H=γn1+H and for 1in2, γ~i+H=γi+γi+1+H. In this scheme, w(eij)=γ~i+H◻

Let us look at a specific example how we would use this lemma to construct a vertex labeling of D53 with Γ=Z5Z3 that would induce a Γ-harmonious labeling. We realize that the group Z5Z3 is in fact isomorphic to Z15, but we are using this example to illustrate how the method works for a group of type ZaZb. It is independent on whether or not the numbers a and b are relatively prime.

Example 3. Γ-harmonious labeling of D53 with Γ=Z5Z3Z15.

Here, we have, H={0}Z3 and K={H,(1,0)+H,(2,0)+H,(3,0)+H,(4,0)+H}. In Figure 3 (a), we have a K-harmonious labeling for each Cj, where u is labeled with H, and in each Cj, vij is labeled with (i,0)+H.

In Figure 3(b), u is labeled with (0,0). We have chosen a distinct element of {0}Z3 for each Cj specifically, h1=(0,0) for C1, h2=(0,1) for C2, and h3=(0,2) for C3. We labeled the vertices vi1 with (1,0)+(0,0),(2,0)+(0,0),(3,0)+(0,0),(4,0)+(0,0). Similarly, we labeled the vertices vi2 with {i,0)+(0,1)} and vertices vi3 with {i,0)+(0,2)}. We can check that this construction produces a Γ-harmonious labeling of D53.

Theorem 21. When n and m are odd, then Dnm is Γ-harmonious for any Abelian group Γ of order mn.

Proof. We will use Observation 20 to construct a vertex labeling f of Dnm with Γ that will induce a Γ-harmonious labeling of Dnm. For every n-cycle Cj, choose a distinct element hj in H. This is possible because |H|=m.

We start by labeling the central vertex u with 0, the identity element of Γ. If a vertex vij in some Cj is labeled with g(vij)=γi+H in the K-harmonious labeling of Cj constructed in Observation 20, then we label it with f(vij)=γi+hj, where hj is the chosen element of H for Cj.

First we want to show that this construction produces a well-defined vertex labeling. Suppose that for some vi1j1vi2j2 we have f(vi1j1)=f(vi2j2).

f(vi1j1)=γi1+hj1=γi2+hj2=f(vi2j2) and

(1)(γi1+hj1)+H=(γi2+hj2)+H. Because hj1,hj2H, we know that (2)(γi1+hj1)+H=γi1+H

and (3)(γi2+hj2)+H=γi2+H. Combining equations 1, 2 and 3, we obtain that γi1+H=γi2+H. But then g(vi1j1)=γi1+H=γi2+H=g(vi2j2)

and we have a contradiction, because in Observation 20 we have shown that g is injective. Moreover, if for some vi0j0 we have f(vi0j0)=γi0+hj0=0, then γi0H, which again contradicts Observation 20. Therefore, this construction induces an injective vertex labeling.

Second, we must check if this construction induces a Γ-harmonious labeling of Dnm. We have to check whether there are any repetitions in the edge labels wf(e) within a blade and across any two blades.

In Cj when wg(eij)=γ~i+H, then wf(eij)=γ~i+khj,where k{1,2}. In particular, for edges uv0j and vn1j we have k=1, otherwise, k=2.

For a fixed j and 0in1, we claim that each wf(eij)=γ~i+khj is distinct. For 1in2, each γ~i+2hj is distinct because each label γ~i+H in Cj was distinct. Moreover, γ~0+hjγ~n1+hj for the same reason.

Now suppose that for a fixed j and some i, 1in2, we have γ~0+hj=γ~i+2hj. Then γ~0=γ~i+hj and wg(e0)=γ~0+H=(γ~i+hj)+H=γ~i+H=wg(ei), which is a contradiction by Observation 20. Similarly for 2in2,wf(en1j)=γ~n1+hjγ~i+2hj=wf(eij).

Finally suppose for 0j1<j2m, and 0i1i2n1 two edge labels wf(ei1j1) and wf(ei2j2) across cycles Cj1 and Cj2 are the same.

Then γ~i1+k1hj1=γ~i2+k2hj2, where k1,k2{1,2}. Then similarly as above we have γ~i1=γ~i2+k2hj2k1hj1=γ~i2+h

for some hH. It follows that wg(ei1)=γ~i1+H=(γ~i2+h)+H=γ~i2+H=wg(ei2), a contradiction again. Thus, each edge label is distinct and the proof is complete. ◻

When n is even, we have a weaker theorem.

Theorem 22. For n even and m odd, Dnm is Γ-harmonious when |Γ|=mn, and Γ has a subgroup H or order m such that K=Γ/H satisfies the conditions in Theorem 8.

Proof. Let m be odd and n be even. If Γ has a subgroup of order m such that K=Γ/H satisfies the conditions in Theorem 8. Then, each Cj is K-harmonious labeling where u is labeled with H. The construction then is same as in Theorem 21. ◻

When m is even, this construction does not work. As discussed in Theorem 21, the label of edge eij is γ~i+khj for k={1,2} and hjH. We know |H|=m. Thus in H, we can have two distinct elements hj and hj such that 2hj=2hj.

7. Generalized Prisms

For generalized prisms, our result is again more general for n odd. This is because even cycles are not Γ-harmonious for all Γ of the proper order, while odd cycles are Γ-harmonious for all Abelian groups Γ of order n (see Theorem 6 or 8).

Recall that the number of edges of the generalized prism Ym,n is (2m1)n. The main idea of our construction is the following. Given a group Γ of order (2m1)n and a subgroup H of Γ of order n satisfying assumptions of Theorem 8 and assume that there is an H-harmonious labeling of Cn. Then we label the vertices of each Cn by elements of a coset β+H where β is a generator of the cyclic quotient group Γ/H in a way corresponding to the original H-harmonious labeling. This way the edge labels of every “layer”, that is, either edges of a particular cycle or all edges between two consecutive cycles form a coset of Γ.

We illustrate the method in two examples.

Example 4. We present a labeling of Y3,5 with Z5Z5, starting with a labeling of C5 with Z5.

Figure 4 Labeling of C5 with Z5
Figure 5 Labeling of C5 with Z5 \oplus \{0\}
Figure 6 Labeling of Y3,5 with Z5 \oplus z5

Example 5. We present a labeling of Y3,8 with Z4Z2Z5, starting with a labeling of C8 with Z4Z2.

Figure 7 Labeling of C8 with Z4 \oplus z2
Figure 8 Labeling of Y3,8 with Z4 \oplus Z2 \oplus z5

Theorem 23. Let n3,m2 and Γ be an Abelian group of order n(2m1). If Γ has a subgroup H of order n that satisfies the assumptions of Theorem 8, and the quotient group Γ/H is cyclic, then prism Ym,nPm◻Cn admits a Γ-harmonious labeling.

Proof. We will use the following notation. Each n-cycle Cj for j=0,1,,m1 will consist of vertices xij with i=1,2,,n and edges xijxi+1j, where i=1,2,,n and addition in the subscript is performed modulo n. The paths Pi will consist of vertices xi0,xi+11,,xi+m1m1 and edges xijxi+1j+1 where i=1,2,,n,j=0,1,,m2 and addition in the subscript is again performed modulo n. Thus, the path edges can be seen as “diagonal”, which is done for computational convenience.

Let H be a subgroup Γ of order n that satisfies the assumptions of Theorem 8 and K=Γ/H be cyclic of order 2m1 generated by a coset β+H.

Hence there exists an H-harmonious labeling g of Cn=x1,x2,,xn. For each xij we now define f(xij)=g(xi)+jβ. Then the label w(xijxi+1j) of an edge xijxi+1j in cycle Cj is defined as w(xijxi+1j)=f(xij)+f(xi+1j)=(g(xi)+jβ)+(g(xi+1)+jβ)=g(xi)+g(xi+1)+2jβ=w(xixi+1)+2jβ. Now the set of all edge labels in Cj is Wj={w(xijxi+1j)i=1,2,,n}={w(xixi+1)+2jβi=1,2,,n}.

Because g is an H-harmonious labeling, the set of all weights w(xixi+1) forms the subgroup H itself and Wj={w(xixi+1)+2jβi=1,2,,n}=2jβ+H, an even coset in Γ/H. Consequently, the labels of all edges in cycles C0,C1,,Cm form all m even cosets H,2β+H,,2(m1)β+H of the cyclic group Γ/H.

For paths, the label of xijxi+1j+1 is defined as w(xijxi+1j+1)=f(xij)+f(xi+1j+1)=(g(xi)+jβ)+(g(xi+1)+(j+1)β)=g(xi)+g(xi+1)+(2j+1)β=w(xixi+1)+(2j+1)β. The set of labels of the path edges between cycles Cj and Cj+1 for j=0,1,,m2 is then Uj={w(xijxi+1j+1)i=1,2,,n}={w(xixi+1)+(2j+1)βi=1,2,,n} the coset (2j+1)β+H. Therefore, the weights of all path edges form all m1 odd cosets β+H,3β+H,,(2m3)β+H of Γ/H.

Because we have j=0,1,,m1, we obtained 2m1 distinct cosets and their union forms the group Γ. This completes the proof. ◻

For convenience, we express the above result in more explicit form, describing the group Γ in the nested form.

Corollary 1. Let n3 be odd, m2 and Γ an Abelian group of order (2m1)n with a cyclic subgroup K of order 2m1. Then the prism Ym,nCn◻Pm admits a Γ-harmonious labeling.

Proof. By Theorem 5 part 2, there exists a subgroup H such that KΓ/H. Indeed, H is of order n and n is odd. Thus, by Theorem 8 there exists a H-harmonious labeling of Cn. The result now follows from Theorem 23. ◻

Corollary 2. Let n4 be even, m2 and Γ an Abelian group of order (2m1)n written in the nested form as Γ=Zn1Zn2Znt where t2, with a cyclic subgroup K of order 2m1. If

  • n10(mod4) and n2 is even, or

  • n24 is even,

then the prism Ym,nCn◻Pm admits a Γ-harmonious labeling.

Proof. By Observation 4, 2m1 divides n1. By Theorem 5 part 2, there is a subgroup H such that KΓ/H. Moreover, H can be written as H=Zn1Zn2Znt, where n1=n1/(2m1).

When n10(mod4) and n2 is even, then also n10(mod4) and H contains a subgroup isomorphic to Z4Z2 and satisfies assumptions of Theorem 6. The result then follows from Theorems 8 and  23.

When n24 is even, then n1 is even as well. And because n24, H contains a subgroup isomorphic to Z2Z2s for s2. Therefore, the result follows again from Theorems 6, 8 and  23. ◻

8. Generalized Web Graphs

For computation convenience, we slightly change the notation here and number the cycles of the generalized prism Ym,n as C1,C2,,Cm.

A generalized closed web is then a graph arising from Ym,n by adding a vertex x00 and joining it by an edge to every vertex of the top cycle C1 of Ym,n. The remaining vertices will follow the notation from Section 7.

The number of edges and order of Γ is now 2mn.

Theorem 24. Let n3,m2 and Γ be an Abelian group of order 2mn. If Γ has a subgroup H of order n that satisfies assumptions of Theorem 8 and the quotient group Γ/H is cyclic, then the generalized closed web CWm,n admits a Γ-harmonious labeling.

Proof. We will use the following notation. The central vertex of degree n will be denoted by x00. Each n-cycle Cj for j=1,2,,m will consist of vertices xij with i=1,2,,n and edges xijxi+1j, where i=1,2,,n and addition in the subscript is performed modulo n. The paths Pi will consist of vertices x00,xi1,xi+12,xi+m2m1 and edges x00xi1 and xi+j1jxi+jj+1 where i=1,2,,n, j=1,2,,m1 and addition in the subscript is again performed modulo n.

The number of edges in CWm,n is 2mn, which implies |Γ|=2mn.

By our assumption, H satisfies conditions of Theorem 8 and therefore there exists an H-harmonious labeling g of Cn=x1,x2,,xn. We first label the central vertex by the identity element of Γ, that is, f(x00)=e. The remaining vertices will be labeled as f(xij)=g(xi)+jβ. Then the label w(xijxi+1j) of an edge xijxi+1j in cycle Cj is defined as w(xijxi+1j)=f(xij)+f(xi+1j)=g(xi)+g(xi+1)+2jβ=w(xixi+1)+2jβ and the set of all edge labels in Cj is Wj={w(xijxi+1j)i=1,2,,n}={w(xixi+1)+2jβi=1,2,,n}=2jβ+H, an even coset in the quotient group Γ/H, because the set of weights of the edges in the cycle Cn forms the subgroup H. This follows from our assumption that H allows an H-harmonious labeling g.

Notice that in the cycle Cm we have Wm=2mβ+H=H, because Γ/H is cyclic of order 2m. Therefore, the labels of all edges in cycles C1,C2,,Cm form all m even cosets H,2β+H,,(2m2)β+H of the cyclic group Γ/H.

For paths, the label of xijxi+1j+1 is defined as w(xijxi+1j+1)=f(xij)+f(xi+1j+1)=g(xi)+g(xi+1)+(2j+1)β=w(xixi+1)+(2j+1)β. The set of labels of the edges incident with the central vertex is U0={w(x00xi1)i=1,2,,n}={f(x00)+f(xi1)i=1,2,,n}={e+g(xi)+βi=1,2,,n}=β+H, because g is the H-harmonious labeling of the cycle Cn and therefore a bijection from the vertex set of Cn to H.

For the remaining path edges, the set of labels between cycles Cj and Cj+1 for j=1,2,,m1 is Uj={w(xijxi+1j+1)i=1,2,,n}={w(xixi+1)+(2j+1)βi=1,2,,n}=(2j+1)+H. Hence, the weights of all path edges form all m odd cosets β+H,3β+H,,(2m1)β+H of Γ/H.

We obtained 2m distinct cosets and their union forms the group Γ. This completes the proof. ◻

Example 6. A Z5Z6-harmonious labeling of the closed web CW3,5.

Figure 9 Labeling of CW3,5 with Z5 \oplus z6

Example 7. A Z4Z2Z6-harmonious labeling of the closed web CW3,8.

Figure 10 Labeling of CW3,8 with Z4 \oplus Z2 \oplus z6

Recall that Seoud and Youssef [9]proved that closed webs CW2,n are harmonious for all odd n. A special case of the previous theorem generalizes their result as follows.

Corollary 3. The closed web CWm,n is harmonious for all odd n3 and any m2.

We again express the previous result of Theorem 24 in terms of the nested form of Γ.

Corollary 4. Let n3 be odd, m2 and Γ an Abelian group of order 2mn with a cyclic subgroup of order 2m. Then the closed web CWm,n is Γ-harmonious.

Proof. Similarly as in the proof of Corollary 1, this follows from Theorems 6, 8, and  24. ◻

For even n, the explicit expression is broken into several cases.

Corollary 5. Let n4 be even, m2 and Γ an Abelian group of order 2mn written in the nested form as Γ=Zn1Zn2Znt where t2, with a cyclic subgroup of order 2m. If

  • n10(mod8m) and n20(mod2), or

  • n10(mod4m), n20(mod2), n24, or

  • n10(mod2m), n20(mod4) and n30(mod2), or

  • n10(mod2m), n30(mod2) and nt>1 is odd,

then the closed web CWm,n is Γ-harmonious.

Proof. We again denote n1=n1/(2m). By similar reasoning as in the proof of Corollary 2, Γ has a subgroup HZn1Zn2Znt.

In Case (1), because n10(mod8m), n10(mod4) and H has a subgroup isomorphic to Z4Z2. Indeed, Γ/H is cyclic of order 2m.

In Case (2), because n10(mod4m), n10(mod2) and H has a subgroup isomorphic to Z2Z2s with s2 because n24.

In Case (3), because n20(mod4) and n30(mod2), H has a subgroup isomorphic to Z4Z2.

Finally, in Case (4), n2 is even because n3 is even. Because nt>1 is odd, we must have n3=2s where snt3, because nt divides n3.

Therefore, the proof again follows from Theorems 6, 8 and 24. ◻

A generalized open web OWm,n is the graph arising from the generalized closed web CWm,n by removing the edges of the bottom n-cycle Cm. The number of edges and order of Γ is then (2m1)n.

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 n3,m2 and Γ be an Abelian group of order (2m1)n. If Γ has a subgroup H of order n that satisfies the assumptions of Theorem 8 and the quotient group Γ/H is cyclic, then the generalized open web OWm,n admits a Γ-harmonious labeling.

Example 8. A Z5Z5-harmonious labeling of the open web OW3,5.

Figure 11 Labeling of OW3,5 with Z5 \oplus Z5

Example 9. A Z4Z2Z5-harmonious labeling of the open web OW3,5.

Figure 12 Labeling of OW3,8 with Z4 \oplus Z2 \oplus z5

Seoud and Youssef [9]and Gnanajothi [6]proved that open webs OWm,n are harmonious for all odd n and m=2 and 3, respectively. We state a generalization following directly from the previous theorem as a corollary.

Corollary 6. The open web OWm,n is harmonious for all odd n and any m2.

For convenience, we again express the result of Theorem 25 in a more explicit form, describing the group Γ in the nested form.

Corollary 7. Let n3 be odd, m2 and Γ an Abelian group of order (2m1)n with a cyclic subgroup of order 2m1. Then the open web OWm,n admits a Γ-harmonious labeling.

Proof. This follows directly from Theorems 6, 8 and  25. ◻

Corollary 8. Let n4 be even, m2 and Γ an Abelian group of order (2m1)n with a cyclic subgroup of order 2m1 written in the nested form as Γ=Zn1Zn2Znt, where t2. If

  • n10(mod4) and n2 is even, or

  • n24 is even,

then the web OWm,n admits a Γ-harmonious labeling.

The proofs are identical to the proofs of Corollaries 1 and 2, respectively.

9. Conclusion

We explored Γ-harmonious labeling, a generalization of a well-known notion of harmonious labeling, for several families of cycles-related graphs. In most cases, our results are only partial. Therefore, we state some open problems here.

There are two main directions for further research. One is dealing with graphs based on even cycles where the group Γ does not contain a subgroup isomorphic to Z4Z2.

Problem 1. Determine for what Abelian groups Γ not containing a subgroup of order n isomorphic to Z2Z2s,s2 there exists a Γ-harmonious labeling of generalized prisms Ym,n, open and closed webs OWm,n, CWm,n and superwheels SWk,n for even n.

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 Γ there exists a Γ-harmonious labeling of Dutch windmill graphs Dnm for even m.

Problem 3. Determine for what Abelian groups Γ there exists a Γ-harmonious labeling of Dutch windmill graphs Dnm for odd m and even n when there does not exist a subgroup H of order m such that K=Γ/H satisfies the conditions in Theorem 8.

The other direction concerns graphs Ym,n and OWm,n when Γ does not have a cyclic subgroup of order 2m1 or CWm,n when Γ does not have a cyclic subgroup of order 2m.

Problem 4. Determine for what Abelian groups Γ not containing a cyclic subgroup

  1. of order 2m1 there exists a Γ-harmonious labeling of generalized prisms Ym,n and open webs OWm,n

  2. of order 2m there exists a Γ-harmonious labeling of closed webs CWm,n.

Acknowledgments

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 Γ-harmonious labeling existed for a given graph and if such labeling existed, it gave us the exact labeling. The program helped us to find counterexamples and investigate patterns. The program can be found here [10].

References:

  1. Graham, R. L. and Sloane, N. J. A., 1980. On additive bases and harmonious graphs. SIAM Journal on Algebraic and Discrete Methods, 1(4), pp.382–404.

  2. Liu, B. and Zhang, X., 1993. On harmonious labelings of graphs. Ars Combinatoria, 36, pp.315–326.

  3. Montgomery, R., Pokrovskiy, A. and Sudakov, B., 2018. Embedding rainbow trees with applications to graph labelling and decomposition. Retrieved from arXiv:1803.03316.

  4. Beals, R., Gallian, J. A., Headly, P. and Jungreis, D., 1991. Harmonious groups. Journal of Combinatorial Theory, Series A, 56(2), pp.223–238.

  5. Gallian, J.A., 2022. A dynamic survey of graph labeling. Electronic Journal of Combinatorics, 6(25), pp.4-623.

  6. Gnanajothi, R. B., 1991. Topics in Graph Theory (Doctoral dissertation). Madurai Kamaraj University.

  7. Gallian, J. A., Prout, J. and Winters, S., 1992. Graceful and harmonious prism related graphs. Ars Combinatoria, 34, pp.213–222.

  8. Jungreis, D. S. and Reid, M., 1992. Labeling grids. Ars Combinatoria, 34, pp.167–182.

  9. Seoud, M. A. and Youssef, M. Z. Harmonious labellings of helms and related graphs [Manuscript]. Retrieved from https://www.researchgate.net/publication/312218305_Harmonious_labelling_of_helms_and_related_graphs?channel=doi&linkId=5877271208ae329d622633c5&showFulltext=true

  10. Koch, J. Gamma-Harmonious-Labeling-Finder. Retrieved from https://github.com/JibJibFlutterhousen/Gamma-Harmonious-Labeling-Finder