# On Harmonious Labeling of Corona Graphs

Authors: Martin Bača; Maged Z. Youssef
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

A graphG with q edges is said to be harmonious, if there is an injection f from the vertices of G to the group of integers modulo q such that when each edge xy is assigned the label f(x)+f(y) (mod q), the resulting edge labels are distinct. In this paper, we study the existence of harmonious labeling for the corona graphs of a cycle and a graph G and for the corona graph of K2 and a tree.


---

## Body

## 1. Introduction

Harmonious graphs naturally arose in the study of modular version of error-correcting codes and channel assignment problems. Graham and Sloane [1] defined a (p,q)-graph G of order p and size q to beharmonious, if there is an injective function f:V(G)→ℤq, where ℤq is the group of integers modulo q, such that the induced function f*:E(G)→ℤq, defined by f*(xy)=f(x)+f(y) for each edge xy∈E(G), is a bijection.The functionf is calledharmonious labeling and the image of f denoted by Im⁡(f) is called the corresponding set of vertex labels.WhenG is a tree or, in general for a graph G with p=q+1, exactly one label may be used on two vertices.Graham and Sloane [1] 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. This necessary condition is called the harmonious parity condition. They also proved that if f is harmonious labeling of a graph G of size q, then so is af+b labeling, where a is an invertible element of ℤq and b is any element of ℤq.Chang et al. [2] define an injective labeling f of a graph G with q edges to bestronglyc-harmonious, if the vertex labels are from the set {0,1,…,q-1} and the edge labels are from the set {f*(xy)=f(x)+f(y):xy∈E(G)}={c,c+1,…,c+q-1}. Grace [3, 4] called such labelingsequential. In the case of a tree, Grace allows the vertex labels to range from 0 up to q. Strongly 1-harmonious graph is called strongly harmonious.By taking the edge labels of a sequentially labeled graph withq edges modulo q, we obviously obtain a harmoniously labeled graph. It is not known if there is a graph that can be harmoniously labeled but not sequentially labeled. More than 50 papers have been published on harmonious labeling and comprehensive information can be found in [5]. Similarly, labeling of special types of crown graphs is examined in [6].In this paper, we study the existence of harmonious labeling for the graphs obtained by corona operation between a cycle and a graphG and also between K2 and a tree or K2 and a unicyclic graph.


## 2. Main Results

In this section, we present the results related to corona graphs. The corona operation between two graphs was introduced by Frucht and Harary [7]. Given two graphs G of order p and H, thecorona of G with H, denoted by G⊙H, is the graph with V(G⊙H)=V(G)∪⋃i=1pV(Hi), and E(G⊙H)=E(G)∪⋃i=1p‍(E(Hi)∪{(vi,u):vi∈V(G)andu∈V(Hi)}). In other words, a corona graph is obtained from two graphs, G of order p and H, taking one copy of G and p copies of H and joining by an edge the ith vertex of G to every vertex in the ith copy of H.Grace [4] showed that C2n+1⊙K1 is harmonious and conjectured that C2n⊙K1 is harmonious. This conjecture has been proved by Liu and Zhang [8] and Liu [9]. Singh in [10, 11] has proved that Cn⊙K2 and Cn⊙K3 are sequential for all odd n>1. Santhosh [12] has shown that Cn⊙P4 is sequential for all odd n≥3.Thejoin of two graphs G and H, denoted by G+H, is the graph where V(G)∩V(H)=∅ and each vertex of G is adjacent to all vertices of H. When H=K1, this is the corona graph K1⊙G.Graham and Sloane [1] showed harmonious labeling of the join of the path Pn and K1, that is, thefanFn=Pn+K1, and harmonious labeling of thedouble fan  Pn+K2¯. Later, Chang et al. [2] gave harmonious labeling of the join of the star Sn and K1.The next result shows that if join of a graphG and K1 is strongly harmonious, then the corona of a cycle and the graph G admitted harmonious labeling.Theorem 1.
LetG be a graph of order p and size q. If G+K1 is strongly harmonious with the 0 label on the vertex of K1, then Cn⊙G is harmonious for all odd n≥3.Proof.
LetG be a (p,q)-graph and G+K1 strongly harmonious with the 0 label on the vertex x∈K1. Then, there exists labeling f:V(G+K1)→{0,…,p+q-1} such that f(x)=0 and the edge labels are from the set {f*(uv)=f(u)+f(v):uv∈E(G+K1)}={1,2,…,p+q}.
Now, forn odd, n≥3, we consider the corona graph Cn⊙G with n(p+1) vertices and Γ=n(p+q+1) edges. Denote the vertices and edges of the cycle Cn such that V(Cn)={x1,x2,…,xn} and E(Cn)={xixi+1:1≤i≤n-1}∪{xnx1}. By the symbol yi, we denote a vertex in the ith copy of G, denoted by Gi, corresponding to the vertex y in G; that is, y∈V(G) and yi∈V(Gi).
We define the vertex labelingg:V(Cn⊙G)→{0,1,…,Γ-1} in the following:
(1)g(xi)=(p+q+1)(i-1),for1≤i≤n,g(yi)=f(y)+(p+q+1)(i-1),for1≤i≤n.
If we denote the join graph G+K1 as G+{x}, then the set of all edge labels of the ith copy of G+{x} consists of the consecutive integers g*(E(Gi+{xi}))={2(p+q+1)(i-1)+1,2(p+q+1)(i-1)+2,…,2(p+q+1)(i-1)+p+q}, 1≤i≤n. For edge labels of the cycle Cn, we have g*(xixi+1)=g(xi)+g(xi+1)=(p+q+1)(2i-1), for 1≤i≤n-1, and g*(xnx1)=g(xn)+g(x1)=(p+q+1)(n-1).
It is not difficult to see that, for1≤i≤(n-1)/2, it is true that(i)
1+max⁡{g*(E(Gi+{xi}))}=(p+q+1)(2i-1)=g*(xixi+1);(ii)
1+g*(xixi+1)=min⁡{g*(E(G((n+1)/2)+i+{x((n+1)/2)+i}))}=(p+q+1)(2i-1)+1 (mod Γ);(iii)
1+max⁡{g*(E(G((n+1)/2)+i+{x((n+1)/2)+i}))}=2(p+q+1)i (mod Γ) and it is equal to g*(x((n+1)/2)+ix((n+1)/2)+i+1) (mod Γ);(iv)
1+g*(x((n+1)/2)+ix((n+1)/2)+i+1) (mod Γ) is equal to the min⁡{g*(E(Gi+1+{xi+1}))}=2(p+q+1)i+1.Moreover, 1+max⁡{g*(E(G(n+1)/2+{x(n+1)/2}))}=0 (mod Γ) and it is equal to g*(x(n+1)/2x(n+3)/2)=0 (mod Γ).
Thus, under the induced mappingg*, all the resulting edge labels are distinct and they get the consecutive integers from 0 up to n(p+q+1)-1 (mod Γ). This concludes the proof.Graham and Sloane [1] have proved that the fans Fm=Pm+K1, m≤7, and the wheels Wm=Cm+K1, m≢2 (mod 3), are strongly harmonious with the 0 label on the vertex of K1. In light of these results and Theorem 1, we have the following corollaries.Corollary 2.
LetCn⊙Pm be the corona graph of a cycle Cn and a path Pm. Then, Cn⊙Pm is harmonious for all odd n≥3 and 1≤m≤7.Corollary 3.
LetCn⊙Cm be the corona graph of two cycles. Then, Cn⊙Cm is harmonious for all odd n≥3 and m≢2 (mod3).Shee [13] has shown that the complete tripartite graph K1,m,k=Km,k+K1, m,k≥1, is strongly harmonious, while Gnanajothi [14] proved that K1,1,m,k=K1,m,k+K1, m,k≥1, is also strongly harmonious. In both cases, the vertex of K1 is labeled by the 0 label. Thus, with respect to Theorem 1, we obtain the following.Corollary 4.
Form,k≥1 and odd n≥3, the corona graph Cn⊙Km,k is harmonious.Corollary 5.
Form,k≥1 and odd n≥3, the corona graph Cn⊙K1,m,k is harmonious.Let one consider the graphs obtained by corona operation between the single edgeK2 and a tree.Theorem 6.
IfT is a strongly c-harmonious tree of odd size q and c=(q+1)/2, then the corona graph K2⊙T is also strongly c-harmonious.Proof.
LetT be a tree of size q with strongly c-harmonious labeling f:V(T)→{0,1,…,q}, where the edge labels are from the set of consecutive integers {f*(e):e∈E(T)}={c,c+1,…,c+q-1}.
Consider the corona graphK2⊙T with vertices x1,x2∈V(K2) and vertices yi∈V(Ti), i=1,2, corresponding to the vertices y∈T, where the vertex xi is incident to every vertex in Ti for i=1,2.
Define now new vertex labelingg:V(K2⊙T)→{0,1,…,4q+2} such that
(2)g(xi)={c+q,fori=1,q+1,fori=2,g(yi)={f(y),fori=1andeveryy∈T,f(y)+c+q+1,fori=2andeveryy∈T.
Thus, Im⁡(g)={0,1,2,…,q,q+1}∪{c+q,c+q+1,c+q+2,…,c+2q,c+2q+1} and, for the edge labels, we have
(3){g*(e):e∈E(T1)}={c,c+1,c+2,…,c+q-1},{g*(x1y1)=g(x1)+g(y1):y1∈V(T1)}={c+q,c+q+1,…,c+2q},g*(x1x2)=g(x1)+g(x2)=c+2q+1,{g*(x2y2)=g(x2)+g(y2):y2∈V(T2)}={c+2q+2,c+2q+3,…,c+3q+2},{g*(e):e∈E(T2)}={3c+2q+2,3c+2q+3,…,3c+3q+1}.
We can see that edge labels form the set of consecutive integers from c up to 3c+3q+1 if and only if max⁡{g*(x2y2)=g(x2)+g(y2):y2∈V(T2)}+1=min⁡{g*(e):e∈E(T2)}; that is, c=(q+1)/2.We know that every caterpillarCatp admits strongly c-harmonious labeling. As an illustration, Figure 1 provides an example of the strongly 5-harmonious labeling of Cat10.Figure 1
Strongly5-harmonious labeling of the caterpillar Cat10.As an immediate consequence of Theorem6, we can state the following corollary.Corollary 7.
LetCatq+1 be a caterpillar of odd size q. If Catq+1 admits strongly (q+1)/2-harmonious labeling, then the corona graph K2⊙Catq+1 also admits strongly (q+1)/2-harmonious labeling.Theorem 8.
LetG be a unicyclic graph of odd size q. If G is a strongly c-harmonious and c=(q-1)/2, then the corona graph K2⊙G is also strongly c-harmonious.Proof.
LetG be a connected (p,q)-graph containing exactly one cycle. Clearly, p=q. Let f:V(G)→{0,1,…,q-1} be strongly c-harmonious labeling with the edge labels from the set of consecutive integers {f*(e):e∈E(G)}={c,c+1,…,c+q-1}.
Ifx1 and x2 are the vertices of K2 and if by the symbol yi we mean a vertex in the ith copy of G corresponding to the vertex y∈V(G), then sets of vertices and edges of the corona graph K2⊙G are as follows: V(K2⊙G)=V(K2)∪V(G1)∪V(G2), E(K2⊙G)={x1x2}∪E(G1)∪{x1y1:y1∈V(G1)}∪E(G2)∪{x2y2:y2∈V(G2)}.
Define new vertex labelingg:V(K2⊙G)→{0,1,…,4q} in the following:
(4)g(xi)={c+q,fori=1,q,fori=2,g(yi)={f(y),fori=1andeveryy∈G,f(y)+c+q+1,fori=2andeveryy∈G.
The image of the vertex labeling g is a union of two sets of consecutive integers Im⁡(g)={0,1,2,…,q}∪{c+q,c+q+1,c+q+2,…,c+2q}. Observe that the edge labels are
(5){g*(e):e∈E(G1)}={c,c+1,c+2,…,c+q-1},{g*(x1y1)=g(x1)+g(y1):y1∈V(G1)}={c+q,c+q+1,…,c+2q-1},g*(x1x2)=g(x1)+g(x2)=c+2q,{g*(x2y2)=g(x2)+g(y2):y2∈V(T2)}={c+2q+1,c+2q+2,…,c+3q},{g*(e):e∈E(T2)}={3c+2q+2,3c+2q+3,…,3c+3q+1}.
The edge labels form the set of consecutive integers from c up to 3c+3q+1 if and only if c+3q+1=3c+2q+2. It is true if c=(q-1)/2. Thus, the labeling g is strongly (q-1)/2-harmonious labeling of the corona graph K2⊙G.An example of the strongly4-harmonious unicyclic graph is presented in Figure 2.Figure 2
Strongly4-harmonious labeling of a unicyclic graph.We know that every odd cycleC2n+1 admits strongly n-harmonious labeling. As consequence of Theorem 8, we have the following.Corollary 9.
The corona graphK2⊙C2n+1, n≥1, is strongly n-harmonious.



---

*Source: 627248-2014-04-03.xml*