Kyungpook Mathematical Journal 2018; 58(4): 747-759  
Odd Harmonious and Strongly Odd Harmonious Graphs
Department of Mathematics, Faculty of Science, Ain Shams University, Abbassia, Cairo, Egypt, e-mail : m.a.seoud@hotmail.com, Department of Basic science, Faculty of Computers and Information, Fayoum University, Fayoum 63514, Egypt, e-mail : hha00@fayoum.edu.eg
*Corresponding Author.
Received: April 12, 2017; Revised: August 12, 2018; Accepted: October 2, 2018; Published online: December 23, 2018.
© Kyungpook Mathematical Journal. All rights reserved.

This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract

A graph G = (V (G), E(G) of order n = |V (G)| and size m = |E(G)| is said to be odd harmonious if there exists an injection f : V (G) → {0, 1, 2, …, 2m−1} such that the induced function f* : E(G) → {1, 3, 5, …, 2m−1} defined by f*(uv) = f(u)+f(v) is bijection. While a bipartite graph G with partite sets A and B is said to be bigraceful if there exist a pair of injective functions fA : A → {0, 1, …, m − 1} and fB : B → {0, 1, …, m − 1} such that the induced labeling on the edges fE(G) : E(G) → {0, 1, …, m − 1} defined by fE(G)(uv) = fA(u)−fB(v) (with respect to the ordered partition (A, B)), is also injective. In this paper we prove that odd harmonious graphs and bigraceful graphs are equivalent. We also prove that the number of distinct odd harmonious labeled graphs on m edges is m! and the number of distinct strongly odd harmonious labeled graphs on m edges is ⌈m/2⌉! ⌊m/2⌋!. We prove that the Cartesian product of strongly odd harmonious trees is strongly odd harmonious. We find some new disconnected odd harmonious graphs.

Keywords: odd harmonious graphs, labeling, cartesian product.
1. Introduction

A graph that has order n and size m is called a (n, m)-graph. Acharya and Hedge in [2] introduced arithmetic graphs. Let G = (V, E) be a finite simple (n, m)-graph, D be a non-negative integer set, and let k and d be positive integers. A labeling f from V to D is said to be (k, d)-arithmetic if the vertex labels are distinct non-negative integers and the edge labels induced by f+(xy) = f(x) + f(y) for each edge xy are k, k+d, k+2d, …, k+(m−1)d. Then G is said to be a (k, d)-arithmetic graph. Liang in [10] called the case where k = 1, d = 2 and D = {0, 1, 2, .., 2m− 1} odd arithmetic labeling. Liang and Bai in [11] called odd arithmetic graphs odd harmonious. In [11], they called the case when D = {0, 1, 2, .., m} strongly odd harmonious graph. Graceful labeling was introduced by Rosa [12] as a means of attacking the problem of cyclically decomposing the complete graph into the trees. An injective vertex function f : V (G) → {0, 1, 2, …, m} is said to be a graceful if f*(uv) =| f(u) − f(v) | from E(G) to {1, 2, 3, …, m} is injective. A graph that admits a graceful labeling is called graceful graph. A graceful graph G is said to be α-valuable if it has a graceful labeling f such that for some positive integer λ either f(u) ≤ λ and f(v) > λ or f(u) > λ and f(v) ≤ λ for every edge uvE(G). λ is said to be the characteristic of f. As in [9], a bipartite graph G(n, m) with partite sets A and B is bigraceful if there exist a pair of injective functions fA : A → {0, 1, …, m − 1} and fB : B → {0, 1, …, m − 1} such that the induced labeling on the edges fE(G) : E(G) → {0, 1, …, m − 1} defined by fE(G)(uv) = fA(u) − fB(v) (with respect to the ordered partition (A, B)), is also injective. For a dynamic survey of graph labeling, we refer to [5]. In [3], authors defined (k, d)-arithmetic as it defined above except they assumed that D = R, i.e f : V (G) → R and f+(E(G)) = {k, k + d, …, k + (m− 1)d} such that f and f+ are both injective, and then proved that every α-labeled graph is (k, d)-arithmetic as follows:

Lemma 1.1

If G has an α-labeling f of characteristic λ. Let V1 = {uV (G) : f(u) ≤ λ} and V2 = {uV (G) : f(u) > λ}. Define g : V (G) → R by

g(u)={-d(f(u)+k)uV1k+df(u)uV2

Then g is a (k, d)-arithmetic vertex function of G and G is (k, d)-arithmetic for all k, dZ+.

Let [0, 2, 1, 4] be an α-labeling of C4. According to (1.1), the (1, 2)-arithmetic labeling of C4 is [−2, 5, −4, 9]. To ensure that vertex labels belong to {0, 1, 2, …, 2m− 1}, We can replace (1.1) with

g(u)={2(λ-f(u))uV12(f(u)-(λ)-1uV2

implies that every α-valuable graph is odd harmonious. Gallian in [5] mentioned that Koppendrayer had proved that if G has an α-labeling, then it is odd harmonious.

Let G = (V (G), E(G)) and H = (V (H), E(H)) be two graphs. The Cartesian product G × H has its vertex set V (G) × V (H) and u = (x1, y1) is adjacent to v = (x2, y2) whenever [x1 = x2 and y1y2E(H)] or [y1 = y2 and x1x2E(G)]. For a graph G the subdivision of graph S(G) is the graph obtained by subdividing every edge of G exactly once. We denote the path on n vertices by Pn.

2. Main Result

In this section, we prove that odd harmonious graphs and bigraceful graphs are equivalent. Then we find the number of odd harmonious labeled graphs.

2.1. Odd harmonious graphs and other labelings

Theorem 2.1

A graph G is odd harmonious if and only if it is bigraceful.

Proof

Let G(n, m) be an odd harmonious graph with labeling f. The set V (G) has a bipartition (A, B), where A = {uV (G) : f(u) = 2i, i ≥ 0} and B = {uV (G) : f(u) = 2i − 1, i ≥ 1}, i.e A is the subset of V (G) with even labels and B is the subset of V (G) with odd labels. Define the bigraceful labeling functions gA and gB as follows: gA : A → {0, 1, …, m − 1}, where gA(u)=f(u)2 and gB : B → {0, 1, …, m − 1}, where gB(u)=m-1-(f(u)-1)2.

It is obvious that both gA and gB are injective.

For each edge uvE(G) with uA and vB we must get gB(v) ≥ gA(u): Assume on contradiction that gB(v) < gA(u). Then m-1-(f(v)-1)2<f(u)2 and f(u) + f(v) > 2m − 1 a contradiction.

Edge uv, where uA and vB, has label gB(v)-gA(u)=m-1-(f(v)-1)2-f(u)2=m-1-f(u)+f(v)-12=m-1-k-12, k = f(u) + f(v). Since 1 ≤ k ≤ 2m − 1, we have 0m-1-k-12m-1, and the edge labels induced by g are {0, 1, 2, …, m − 1}.

Conversely, let G(n, m) be a bigraceful bipartite graph with partite sets A and B with labeling functions gA : A → {0, 1, .., m − 1} and gB : B → {0, 1, .., m − 1} such that gB(u) ≥ gA(v) for each edge uv with uB and vA. Define the odd harmonious labeling function f as follows:

f(u)={2m-2gB(u)-1uB2gA(u)uA

Since both gA and gB are injective, f is injective and f(V (G)) ⊆ {0, 1, …, 2m− 1}.

Edge uv with uA and vB has label f(u) + f(v) = 2gA(u) + 2m − 2gB(v) − 1 = 2m − 2(gB(v) − gA(u)) − 1 = 2m − 2k − 1, k = gB(v) − gA(u). Since 0 ≤ km − 1, we must have f+(E(G)) = {1, 3, …, 2m − 1}.

It is shown in [9] that if G(n, m) is bigracful, then the complete bipartite graph Km,m has a cyclic decomposition into isomorphic copies of G.

Corollary 2.2

If G(n, m) is odd harmonious, then Km,m has a cyclic decomposition into copies isomorphic to G.

Corollary 2.3

If G is a strongly odd harmonious graph, then G has an αlabeling.

Proof

Assume G(n, m) be a strongly odd harmonious graph with labeling f and the bipartition of V (G) as in the proof of theorem 2.1. Define the α-labeling function g : V (G) → {0, 1, 2, …, 2m − 1} as follows:

g(u)={f(u)2uAm-f(u)-12uB

It is not difficult to prove that g is an α-labeling for G with characteristic m2 when m even and m-12 when m odd.

Hence, if G(n, m) is strongly odd harmonious then it decomposes both K2m+1 and Km,m.

Remark 2.4

The converse of corollary 2.2 is not true, since km,n, with mn odd, is α-labeled but not strongly odd harmonious.

If G is odd harmonious graph, then the maximum label of all vertices is at most 2m−2δ(G)+1, where δ(G) is the minimum degree of the vertices of G.

Let T be a tree that is α-labeled. Then T is strongly odd harmonious iff V (T) has a bipartition (A, B) such that ||A| − |B|| ≤ 1.

2.2. Counting labeled graphs

Theorem 2.5

There are m! distinct odd harmonious labeled graphs on m edges.

Proof

An odd harmonious graph on m edges must have edge labeled 1, edge labeled 3,· · ·, and edge labeled 2m − 1. If an edge e has label 2i − 1, for 1 ≤ i ≤ 2m − 1, then we must have vertex labeled r adjacent to one labeled s, where r +s = 2i−1. Since we have the following partition of odd numbers:

1=0+1,3=0+3=1+2,5=0+5=1+4=2+3,7=0+7=1+6=2+5=3+4,2m-1=0+(2m-1)=1+(2m-2)=2+(2m-3)==(m-1)+m.

Since, in an odd harmonious graph with m edges, we must select exactly one representation for every odd number in {1, 3, 5, …, 2m − 1} from the above partition of odd numbers, the number of distinct odd harmonious labeled graphs on m edges is m!.

Theorem 2.6

There arem2!m2!distinct strongly odd harmonious labeled graphs on m edges.

Proof

Assume without loss of generality that m is odd. In strongly odd harmonious graphs, the maximum vertex label is m and we have the following partition of the odd numbers:

2m-1=m+m-1,2m-3=[m+(m-3)]=[(m-1)+(m-2)],2m-5=m+(m-5)=(m-1)+(m-4)=(m-2)+(m-3),         m=[(m-1)+0]=[(m-2)+1]==[m/2+m/2],m-2=[(m-2)+0]=[(m-3)+1]==[(m-2)/2+(m-2)/2],         3=[3+0]=[1+2],1=1+0,

which completes the proof.

By the same technique used in the proof of theorem 2.5 and theorem 2.6 we can prove that the number of distinct odd graceful labeled graphs [7], distinct even harmonious labeled graphs [13] and distinct strongly even harmonious labeled graphs [6] on m edges is Πi=1m(2i-1), mm and m!, respectively.

3. Some Odd Harmonious Graphs

We will use the △+1-construction defined in [4, 8] to produce new strongly odd harmonious trees and prove that the Cartesian product of strongly odd harmonious trees is strongly odd harmonious. For two trees T1 and T2, let T1T2 be the tree obtained by identifying a distinguished vertex v* from T2 to each vertex of T1. First we prove that T1T2 is strongly odd harmonious provided that T1 and T2 are strongly odd harmonious.

Theorem 3.1

If T1and T2are strongly odd harmonious trees, then the graph T1T2is strongly odd harmonious.

Proof

Let T1 and T2 be two strongly odd harmonious trees on n and m vertices, respectively. Let f be a strongly odd harmonious labeling of T2 and f′ be the strongly odd harmonious labeling defined by f′(x) = m − 1 − f(x), for xV (T2). Denote the vertices of T2 by x0, x1, …, xm−1 such that f(xi) = i. Let T0, T1, …, Tn−1 be n distinct copies of T2 and V (Ti) = {xij, 1 ≤ jm} for 0 ≤ in − 1, where xij is the corresponding vertex to xj. Let xj be an arbitrary fixed vertex in T2 and denote it by xj*. Let xij* be the corresponding to xj* in the copy Ti. Based upon the strongly odd harmonious labeling of the tree T1, we adjoin the copy Ti of T2 to vertex labeled i of T1 in such a manner that xij* and the vertex labeled i are identified (See Figure 1). Note that V (T1T2) = {x01, x02, …, x0(m−1)} ∪ {x11, x12, …, x1(m−1)} …∪ {x(n−1)1, x(n−1)2, …, x(n−1)(m−1)}. Label the vertices of T1T2 in the following manner:g(x0j) = f(x0j) = f(xj) = j, j = 0, 1, 2, …, m−1, g(xij) = f(x0j) + im = f(xj) + im = j + im, when i is even and 2 ≤ in − 1, g(xij) = f′(x0j)+im = f′(xj)+im = m−1−j+im, when i is odd and 1 ≤ in−1. We prove that this labeling function g is strongly odd harmonious.

Obviously g is injective. Edges of T1T2 are those either joining the copies Ti of T2 or an edge in a copy Ti. Edge joining Ti and Tj has label m(i + j + 1) − 1, where i + j is an edge label in T1. Edges in Ti have labels {2mi + 1, 2mi + 3, …, 2mi + 2m − 3} for 0 ≤ in − 1. What remains is to prove that edge labels are distinct. For this, assume that an edge joining Ti and Tj has the same label as an edge in Tk, i.e m(i+j+1)−1 = 2mk+l, for i+j = s is an edge label in T1 and l is an edge label in T2 for 0 ≤ kn−1. Which implies that l = m(s+1)−2mk−1 = m(s+1−2k) −1. If s = 2r −1 for some positive integer r, then l = 2m(rk) −1 which can’t happen.

Note that if we replace the tree T2 in theorem 3.1 by any other strongly odd harmonious graph, the result still true. Moreover, if we replace the edge xij*xkj* in T1T2 with any other edge joining corresponding vertices(other than xij* and xkj*) in Ti and Tk we get the generalized T1T2 construction. △+1-construction depends upon making the △-construction on T1v, where v is the vertex with maximum label in T1, then adding a vertex to the new graph. We prove the following theorem using △+1-construction.

Theorem 3.2

If T is a strongly odd harmonious tree, then the subdivision graph of T is strongly odd harmonious.

Proof

Let T1 = T and T2 = P2, the path on two vertices. Let f1, f2 be a strongly odd harmonious labelings of T1 and T2, respectively. Let x be the vertex in T1 with f1(x) = n − 1, where n is the number of vertices of T1. Remove x from T1 and construct the generalized (T1x) △ T2 construction in the following manner. Denote the vertices of P2 by v1 and v2. Assume without any loss of generality that f2(v1) = 0 and f2(v2) = 1. Let T0, T1,…, Tn−2 be n − 1 distinct copies of T2 and V (Ti) = {vij, 1 ≤ j ≤ 2} for 0 ≤ in−2, where the vertex vij is the corresponding vertex to vj, j = 1, 2. Based upon the strongly odd harmonious labeling of the tree T1, we replace the vertex labeled i of T1 by the copy Ti of T2. Label the vertices of Ti with g(v0j) = f2(v0j) = f2(vj) and g(vij) = f(v0j) + 2i = f2(vj) + 2i. Now we add a vertex u and label it with g(u) = 2n − 2. If f1(N(x)) = {x1, x2, …, xk}, we join the vertex u to {vx12, vx22, …, vxk2}. Denote by ui the vertex labeled i in T1, i = 0, 1, 2, …, n − 2. If uiuj is an edge in T1 and dT1 (ui, x) = dT1 (uj, x) + 1, join vi2 to vj1. The resulting graph is T1+1T2. Note that the difference between labeling function here and that in the proof of Theorem 3.1 is that we didn’t use f′ of T2 = P2, this is to make the joining of the copies of T2 easy. Moreover, the edges incident with u have labels in the form 2s+1, where s is a label of an edge incident with x in T1. Hence g is strongly odd harmonious labeling of S(T) = T1+1T2.(See Figure 2)

Moreover, if we replace the tree T2 = P2 with a path on l vertices we would obtain, following the same proof, Sl(T) is strongly odd harmonious, where Sl(T) is the tree obtained by inserting l new vertices into each edge of T. The following lemma generalizes the result that Pn ×Pm is odd harmonious proved by Liang and Bai [11].

Lemma 3.3

If Tn and Tm are strongly odd harmonious trees on n and m vertices respectively, then the graph Tn × Tm is strongly odd harmonious.

Proof

Let f1 and f2 be strongly odd harmonious labelings of Tn and Tm, respectively. Denote the vertices of Tn by x1, x2, …, xn. Let T0, T1, T2, …, Tm−1 be m distinct copies of Tn. Let V (Ti) = {xij |j = 1, 2, …, n}, 0 ≤ im−1, where xij is the corresponding vertex to xj. Based upon the strongly odd harmonious labeling of Tm, we replace vertex labeled i by Ti and join corresponding vertices in the distinct copies of Tn to obtain the graph Tn ×Tm, i.e. if uv is an edge in Tm such that f1(u) = i and f1(v) = j, join the corresponding vertices in Ti and Tj. Label the vertices of T0 with f1 and the vertices of Ti with g(xij) = f1(x0j) + i(2n − 1), for 1 ≤ im− 1. In what remains we prove that the described labeling of Tn × Tm is strongly odd harmonious. Because f1 is injective, g is injective and the maximum label assigned to the vertices is n−1+(m−1)(2n−1) = 2mn−(m+n) =| E(Tn×Tm) |. Edges in Ti have labels {2i(2n−1)+1, 2i(2n−1)+3, …, 2i(2n−1)+2n−3}. Edge labels in between that in Ti and Ti+1, are the labels assigned to the edges joining Tl and Ts, where l and s are vertex labels assigned by f2 in Tm to produce the edge label i + (i + 1), e.g edge labels in between that in T1 and T2 are labels assigned to the edges joining either T0 and T3 or T1 and T2 according to f2, because in the strongly odd harmonious labeling of Tm, we must have either vertex labeled 0 is adjacent to one labeled 3 or vertex labeled 1 is adjacent to one labeled 2.

Lemma 3.3 would be generalized by replace T1, T2 or both with any strongly odd harmonious graph G(n, n − 1). Following the same technique in the proof of lemma 3.3, the proof of the following lemma is direct.

Lemma 3.4

If G1(n1, n1 − 1) and G2(n2, n2 − 1) are a strongly odd harmonious graphs, then the graph G1 × G2is strongly odd harmonious.

Lemma 3.5

If T is a strongly odd harmonious tree, then the subdivision graph of T × Pm is odd harmonious.

Proof

Let T has n vertices. It is obvious from theorem 3.2 that S(T) has 2n − 1 vertices and has a strongly odd harmonious labeling that assigns the vertices of T the even labels {0, 2, 4, …, 2n−2}. Describe T×Pm as in lemma 3.3, where we assume the strongly odd harmonious labeling of Pm, f2(xi) = i−1, for 1 ≤ im. Let wij be the newly added vertices to the edges of Ti and yij be the newly added vertex between xij and x(i+1)j (see Figure 3). Let f be the strongly odd harmonious labeling of S(Tn). Label the vertices of S(T0) with f. Hence f(V (T0)) = {0, 2, 4, …, 2n − 2} and f({w0j, j = 1, 2, …, n−1}) = {1, 3, 5, …, 2n−3}. Let g be the following labeling of the vertices of S(T × Pm):

g(xij) = f(x0j) + 2in.

g(wij) = 6ni + f(w0j) − 4i.

g(yij) = 6n(i + 1) − 4j − 4i − 1.

g is injective: It is obvious that g(xij) is even, while g(wij) and g(yij) are odd, for all i and j. Hence it is sufficient to show that g(wij) ≠ g(yst) for some i, j, s and t. If it happen g(wij) = g(yst), it would imply that 6ni + f(w0j) − 4i = 6n(s+1)−4t−4s−1 and we get f(w0j) = (6n−4)(si)+6n−4t−1. We distinguish between two cases:

If is: we must have f(w0j) > (6n−4)+6n−4t−1 > 2n−3. Note that f(w0j) ∈ {1, 3, 5, …, 2n − 3} and 1 ≤ tn.

If i > s: we must have f(w0j) < 0.

For all uV (S(T × Pn)), we have g(u) ≤ 6n(m − 1) + 2n − 3 − 4(m − 1) < 2(4nm − 2(n + m)) − 1.

Edges in Ti have labels {8in − 4i + 1, 8in − 4i + 3, …, 8in + 4n − 4i − 5} and edges joining Ti and Ti+1 have labels {8ni+4n−4i−3, 8ni+4n−4i− 1, …, 8in + 8n − 4 − 4i − 1} which all are distinct.

Corollary 3.6

If T is a strongly odd harmonious tree, then the graph S(T × Pm) is α-labeled.

Proof

According to lemma 3.5, S(T × Pm) has an odd harmonious labeling g. Note that S(Tn × Tm) has 3nm − (n + m) vertices and 4nm − 2(n + m) edges. V (S(T × Pm)) has a bipartition (A, B), where A = {xij} and B = {wij, yij} for 0 ≤ im − 1 and 1 ≤ jn. We Define the labeling function h as follows:

h(u)={g(u)2uA4nm-2(n+m)-g(u)-12uB

Since maxuAh(u)=g(x(m-1)n)2=nm-1 and maxuBh(u)=4nm-2(n+m)-g(w(m-1)(n-1))-12=nm. Hence h is an α-labeling with characteristic nm − 1.

The following lemma generalizes result in [14] that C4m×Pn is odd harmonious.

Lemma 3.7

If T is a strongly odd harmonious tree, then the graph C4m × T is strongly odd harmonious.

Proof

We follow the same technique in the proof lemma 3.3, let T be a tree that is strongly odd harmonious with n vertices and C0, C1,…, Cn−1 be n distinct copies of C4m. Denote the vertices of C4m by x1, x2,…, x4m. Assume the following two labelings of C4m: f1:[0, 1, 2, 3, …, 2m−1, 2m+2, 2m+1, 2m+4, 2m+3, …, 4m, 4m−1] and f2:[4m−1, 0, 1, 2, …., 2m−1, 2m+2, 2m+3, 2m+4, …, 4m] for [x1, x2, …, x4m] respectively. Let f be a strongly odd harmonious labeling of T. Remark that f uses all the labels in {0, 1, 2, …, n−1}. In the strongly odd harmonious labeling of T, we replace vertex labeled i by Ci. Based upon the strongly odd harmonious labeling of T join corresponding vertices in the distinct copies of C4m to obtain the graph C4m ×T. Label the vertices of C2l with g(xi) = f1(xi)+8m(2l) and the vertices of C2l−1 with g(xi) = f2(xi)+8m(2l−1) for l such that 2l and 2l−1 ∈ {0, 1, 2, …, n−1}. It is not difficult to show that g is strongly odd harmonious labeling.

Let(P2 × Pm)Pn denote the graph obtained by adding a pendant path Pn to each vertex of P2 × Pm.

Lemma 3.8

All graphs of the form (P2 × Pm)Pnare strongly odd harmonious.

Proof

Let P1, P2,…, Pm be distinct m copies of P2n+2, the path with 2n+2 vertices. Denote the vertices of P2n+2 by x1, x2,…, x2n+2. Assume the labeling of P1 :f1(xj) = j − 1, for 1 ≤ j ≤ 2n + 2. Label the vertices of Pi by f(xj) = (i − 1)(2n + 3) + f1(xj ), for 2 ≤ im. Now joining the two vertices xn+1 and xn+2 in Pi to their correspondences in Pi+1 for 1 ≤ im − 1, we get the strongly odd harmonious labeling of (P2 × Pm)Pn.

4. Disconnected Odd Harmonious Graphs

There is no strongly odd harmonious forest because for any forest on n vertices and m edges we must have mn − 2. Since all odd harmonious graphs on 3 edge are P4 and K1,3, any odd harmonious graph on m ≥ 4 edges must contain at least one of them as a subgraph. According to remark 2.4, for Pn any α-labeling is equivalent to a strongly odd harmonious labeling. It is shown in [1] that:

Lemma 4.1.([1])

If 1 ≤ rn−1, then there exists an α-labeling of P2n−1that assigns the end vertices labels r and r + n.

If 1 ≤ rn, then there exists an α-labeling of P2n that assigns the end vertices labels r and nr.

In strongly odd harmonious labeling of Pn, we have the following lemma.

Lemma 4.2

If r is even and 1 ≤ rn − 1, then there exists a strongly odd harmonious labeling of P2n−1that assigns the end vertices labels r and 2n − 2 − r.

If 1 ≤ rn, then there exists a strongly odd harmonious labeling of P2n that assigns the end vertices labels r and 2n − 1 − r.

We will use lemma 4.2 to prove the following theorem.

Theorem 4.3

If G is (strongly) odd harmonious graph and k is the smallest label that is not assigned to any vertex of G, then GPl is (strongly) odd harmonious, when lk + 2.

Proof

Let G(n, m) be an (a strongly) odd harmonious graph with labeling f and k be the smallest label that is not assigned by f to any vertex of G. Denote the vertices of G by [x1, x2, …, xn] and the vertices of Pl by [y1, y2, …, yl]. We construct the strongly odd harmonious labeling of Pl−1 that assigns end vertices labels lk − 2 and l−2−(lk−2) = k by lemma 4.2. In the strongly odd harmonious labeling of Pl−1, we join a vertex labeled l−1+k to the end vertex labeled lk −2 to obtain the odd harmonious labeling of Pl:[l − 1 + k, lk − 2, …, k]. Label the vertices of G with g, where g(xi) = f(xi) + l − 1. Obviously g is (strongly) odd harmonious labeling function.

Corollary 4.4

The graph C4mPn is strongly odd harmonious for n ≥ 2m + 2.

The graph (C4m × T) ∪ Pn is strongly odd harmonious when n ≥ 2m + 2, where T is a strongly odd harmonious tree.

The graph (C4mPnT is strongly odd harmonious, where T is a strongly odd harmonious tree, when n ≥ 2m + 2.

The graph K1,tPn is odd harmonious iff n ≥ 4.

The graph Tn ×TmPl is strongly odd harmonious when ln+2, where Tn and Tm are strongly odd harmonious trees on n and m vertices respectively.

Proof

Denote the vertices of C4m by [x1, x2, …, x4m]. Assume the strongly odd harmonious labeling of C4m: f1 = [0, 1, 2, …, 2m − 1, 2m + 2, 2m + 1, 2m + 4, 2m + 3, …, 4m, 4m − 1] for [x1, x2, …, x4m]. Remark that f1 does not assign any vertex the label 2m. Hence in theorem 4.3 by letting G = C4m the result holds.

By lemma 3.7, the strongly odd harmonious labeling described there not assign the label 2m to any vertex in C4m × Tn.

The same as the proof of lemma 3.3 by setting T1 = C4mPn with labeling in corollary 4.4(1) and the result holds immediately.

Denote the vertices of K1,t by [x, x1, x2, …, xt], where x is the center vertex. Since K1,t has the labeling f : [0, 1, 3, 5, …, 2t−3] which not assign the label 2 to any vertex, theorem 4.3 would imply that K1,tPn is odd harmonious when n ≥ 4. When n ≤ 3 we prove a more general result that the union of two bistars is not odd harmonious. Let K1,n and K1,m be two bistars. It is known that K1,i has only the two odd harmonious labelings fi : [0, 1, 3, 5, …, 2i−3] and gi : [1, 0, 2, 4, …, 2i − 2] for i = n, m. Because of the partition of odd numbers in the proof of theorem 2.5 one of the two bistars should has one of the two labelings fi and gi. Assume without loss of generality that K1,n has the labeling fn : [0, 1, 3, 5, …, 2n−3] then the edge label 2n−1 can’t be obtained.

By lemma 3.3, the strongly odd harmonious labeling described there not assign the label n to any vertex in Tn × Tm.

We note here that the graph C4mPn is odd harmonious for all n, m. Actually it is proven in [15] that C4mPn has an α-labeling, for n ≤ 4m−4 and m ≥ 2, and so is odd harmonious. According to corollary 4.4 the remaining cases are C8P5, C4P2 and C4P3. If the vertices of C4mPn are denoted by [x1, x2, …, x4m] ∪ [y1, y2, …, yn], then the odd harmonious labeling of C8P5, C4P3 and C4P2 is [0, 1, 2, 3, 4, 7, 6, 9] ∪ [10, 11, 12, 5, 14], [0, 1, 4, 3] ∪ [9, 2, 7] and [0, 1, 4, 3] ∪ [2, 7] respectively. Also, we note that the graph C4C4C4 has no α-labeling, but it is odd harmonious. Label the three cycles [5,2,1,0], [8,7,4,15], [10,11,6,3].

Lemma 4.5

If G be a strongly odd harmonious (n, m)-graph that is not a tree, then the graph K1,tG is odd harmonious.

Proof

Let f be a strongly odd harmonious labeling of G, define the labeling g of the vertices of K1,tG in the following manner: g(u) = f(u) if uV (G). Let x be the largest number in {0, 1, 2, …, m} that is not assigned by f to any vertex of G. Label the center of K1,t with x. Let y = 2m+1−x. Label the vertices of K1,t with [y, y + 2, y + 4, …, y + 2t − 2]. Note that m + 3 ≤ y ≤ 2m − 1 and the maximum label assigned to a vertex in K1,t is at most 2m+2t−3. Edges in G have labels {1, 3, 5, …, 2m−1} and edges in K1,t have labels {2m+1, 2m+3, …, 2m+2t−1}.

Acknowledgements

The authors would like to thank the anonymous referees for their useful suggestions and comments.

Figures
Fig. 1. T1T2 with T1 is the bistar B2,2 and T2 is the path on 3 vertices
Fig. 2. The subdivision graph (left) of the bistar B2,2 (right)
Fig. 3. S(P4 × P2) odd harmonious labeling
References
  1. Abrham, J (1993). Existence theorems for certain types of graceful valuations of snakes. Congr Numer. 93, 17-22.
  2. Acharya, BD, and Hegde, SM (1990). Arithmetic graphs. J Graph Theory. 14, 275-299.
    CrossRef
  3. Acharya, BD, and Hegde, SM (1991). On certain vertex valuations of a graph I. Indian J Pure Appl Math. 22, 553-560.
  4. Burzio, M, and Ferrarese, G (1998). The subdivision graph of a graceful tree is a graceful tree. Discrete Math. 181, 275-281.
    CrossRef
  5. Gallian, JA (2017). A dynamic survey of graph labeling. Electron J Combin. 20.
  6. Gallian, JA, and Schoenhard, LA (2014). Even harmonious graphs. AKCE Int J Graphs Comb. 11, 27-49.
  7. Gnanajothi, RB 1991. Topics in graph theory. Ph D Thesis. Madurai Kamaraj University.
  8. Koh, KM, Tan, T, and Rogers, DG (1979). Two theorems on graceful trees. Discrete Math. 25, 141-148.
    CrossRef
  9. Liadó, A, and Lopez, SC (2005). Edge-decompositions of Kn,n into isomorphic copies of a given tree. J Graph Theory. 48, 1-18.
    CrossRef
  10. Liang, ZH (2008). On Odd Arithmetic Graphs. J Math Res Exposition. 28, 706-712.
  11. Liang, ZH, and Bai, ZL (2009). On the odd harmonious graphs with applications. J Appl Math Comput. 29, 105-116.
    CrossRef
  12. Rosa, A (1966). On certain valuations of the vertices of a graph. Theory Graphs, Int Symp Rome, pp. 349-355
  13. Sarasija, PB, and Binthiya, R (2011). Even harmonious graphs with applications. International journal of computer science and information security. 9, 161-163.
  14. Saputri, GA, Sugeng, KA, and Froncek, D (2013). The odd harmonious labeling of dumbbell and generalized prism graphs. AKCE Int J Graphs Comb. 10, 221-228.
  15. Traetta, T (2013). A complete solution to the two-table Oberwolfach problems. J Combin Theory Ser A. 120, 984-997.
    CrossRef


This Article

Social Network Service

e-submission

Archives

Indexed/Covered by