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

Corollary 2.2

If G(n, m) is odd harmonious, then K_m,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.

Remark 2.4

• The converse of corollary 2.2 is not true, since k_m,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.

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:

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!.

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:

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), m^m and m!, respectively.

Let T₁ and T₂ be two strongly odd harmonious trees on n and m vertices, respectively. Let f be a strongly odd harmonious labeling of T₂ and f′ be the strongly odd harmonious labeling defined by f′(x) = m − 1 − f(x), for x ∈ V (T₂). Denote the vertices of T₂ by x₀, x₁, …, x_m−1 such that f(x_i) = i. Let T₀, T₁, …, Tⁿ⁻¹ be n distinct copies of T₂ and V (T_i) = {x_ij, 1 ≤ j ≤ m} for 0 ≤ i ≤ n − 1, where x_ij is the corresponding vertex to x_j. Let x_j be an arbitrary fixed vertex in T₂ and denote it by xj*. Let xij* be the corresponding to xj* in the copy Tⁱ. Based upon the strongly odd harmonious labeling of the tree T₁, we adjoin the copy Tⁱ of T₂ to vertex labeled i of T₁ in such a manner that xij* and the vertex labeled i are identified (See Figure 1). Note that V (T₁ △ T₂) = {x₀₁, x₀₂, …, x_0(m−1)} ∪ {x₁₁, x₁₂, …, x_1(m−1)} …∪ {x_(n−1)1, x_(n−1)2, …, x_{(n−1)(m−1)}}. Label the vertices of T₁△T₂ in the following manner:g(x_0j) = f(x_0j) = f(x_j) = j, j = 0, 1, 2, …, m−1, g(x_ij) = f(x_0j) + im = f(x_j) + im = j + im, when i is even and 2 ≤ i ≤ n − 1, g(x_ij) = f′(x_0j)+im = f′(x_j)+im = m−1−j+im, when i is odd and 1 ≤ i ≤ n−1. We prove that this labeling function g is strongly odd harmonious.

Obviously g is injective. Edges of T₁△T₂ are those either joining the copies Tⁱ of T₂ or an edge in a copy Tⁱ. Edge joining Tⁱ and T^j has label m(i + j + 1) − 1, where i + j is an edge label in T₁. Edges in Tⁱ have labels {2mi + 1, 2mi + 3, …, 2mi + 2m − 3} for 0 ≤ i ≤ n − 1. What remains is to prove that edge labels are distinct. For this, assume that an edge joining Tⁱ and T^j has the same label as an edge in T^k, i.e m(i+j+1)−1 = 2mk+l, for i+j = s is an edge label in T₁ and l is an edge label in T₂ for 0 ≤ k ≤ n−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(r − k) −1 which can’t happen.

Note that if we replace the tree T₂ in theorem 3.1 by any other strongly odd harmonious graph, the result still true. Moreover, if we replace the edge xij*xkj* in T₁△T₂ with any other edge joining corresponding vertices(other than xij* and xkj*) in Tⁱ and T^k we get the generalized T₁△T₂ construction. △₊₁-construction depends upon making the △-construction on T₁ – v, where v is the vertex with maximum label in T₁, then adding a vertex to the new graph. We prove the following theorem using △₊₁-construction.

Let T₁ = T and T₂ = P₂, the path on two vertices. Let f₁, f₂ be a strongly odd harmonious labelings of T₁ and T₂, respectively. Let x be the vertex in T₁ with f₁(x) = n − 1, where n is the number of vertices of T₁. Remove x from T₁ and construct the generalized (T₁ − x) △ T₂ construction in the following manner. Denote the vertices of P₂ by v₁ and v₂. Assume without any loss of generality that f₂(v₁) = 0 and f₂(v₂) = 1. Let T⁰, T¹,…, Tⁿ⁻² be n − 1 distinct copies of T₂ and V (Tⁱ) = {v_ij, 1 ≤ j ≤ 2} for 0 ≤ i ≤ n−2, where the vertex v_ij is the corresponding vertex to v_j, j = 1, 2. Based upon the strongly odd harmonious labeling of the tree T₁, we replace the vertex labeled i of T₁ by the copy Tⁱ of T₂. Label the vertices of Tⁱ with g(v_0j) = f₂(v_0j) = f₂(v_j) and g(v_ij) = f(v_0j) + 2i = f₂(v_j) + 2i. Now we add a vertex u and label it with g(u) = 2n − 2. If f₁(N(x)) = {x₁, x₂, …, x_k}, we join the vertex u to {v_x12, v_x22, …, v_xk2}. Denote by u_i the vertex labeled i in T₁, i = 0, 1, 2, …, n − 2. If u_iu_j is an edge in T₁ and d_T1 (u_i, x) = d_T1 (u_j, x) + 1, join v_i2 to v_j1. The resulting graph is T₁ △₊₁T₂. 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 T₂ = P₂, this is to make the joining of the copies of T₂ 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 T₁. Hence g is strongly odd harmonious labeling of S(T) = T₁△₊₁T₂.(See Figure 2)

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

Let f₁ and f₂ be strongly odd harmonious labelings of T_n and T_m, respectively. Denote the vertices of T_n by x₁, x₂, …, x_n. Let T⁰, T¹, T², …, T^m−1 be m distinct copies of T_n. Let V (Tⁱ) = {x_ij |j = 1, 2, …, n}, 0 ≤ i ≤ m−1, where x_ij is the corresponding vertex to x_j. Based upon the strongly odd harmonious labeling of T_m, we replace vertex labeled i by Tⁱ and join corresponding vertices in the distinct copies of T_n to obtain the graph T_n ×T_m, i.e. if uv is an edge in T_m such that f₁(u) = i and f₁(v) = j, join the corresponding vertices in Tⁱ and T^j. Label the vertices of T⁰ with f₁ and the vertices of Tⁱ with g(x_ij) = f₁(x_0j) + i(2n − 1), for 1 ≤ i ≤ m− 1. In what remains we prove that the described labeling of T_n × T_m is strongly odd harmonious. Because f₁ is injective, g is injective and the maximum label assigned to the vertices is n−1+(m−1)(2n−1) = 2mn−(m+n) =| E(T_n×T_m) |. Edges in Tⁱ have labels {2i(2n−1)+1, 2i(2n−1)+3, …, 2i(2n−1)+2n−3}. Edge labels in between that in Tⁱ and Tⁱ⁺¹, are the labels assigned to the edges joining T^l and T^s, where l and s are vertex labels assigned by f₂ in T_m to produce the edge label i + (i + 1), e.g edge labels in between that in T¹ and T² are labels assigned to the edges joining either T⁰ and T³ or T¹ and T² according to f₂, because in the strongly odd harmonious labeling of T_m, 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 T₁, T₂ 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.

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×P_m as in lemma 3.3, where we assume the strongly odd harmonious labeling of P_m, f₂(x_i) = i−1, for 1 ≤ i ≤ m. Let w_ij be the newly added vertices to the edges of Tⁱ and y_ij be the newly added vertex between x_ij and x_(i+1)j (see Figure 3). Let f be the strongly odd harmonious labeling of S(T_n). Label the vertices of S(T⁰) with f. Hence f(V (T⁰)) = {0, 2, 4, …, 2n − 2} and f({w_0j, j = 1, 2, …, n−1}) = {1, 3, 5, …, 2n−3}. Let g be the following labeling of the vertices of S(T × P_m):

• g(x_ij) = f(x_0j) + 2in.

• g(w_ij) = 6ni + f(w_0j) − 4i.

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

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

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

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

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

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

According to lemma 3.5, S(T × P_m) has an odd harmonious labeling g. Note that S(T_n × T_m) has 3nm − (n + m) vertices and 4nm − 2(n + m) edges. V (S(T × P_m)) has a bipartition (A, B), where A = {x_ij} and B = {w_ij, y_ij} for 0 ≤ i ≤ m − 1 and 1 ≤ j ≤ n. We Define the labeling function h as follows:

Since maxu∈A h(u)=g(x(m-1)n)2=nm-1 and maxu∈B h(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 C_4m×P_n is odd harmonious.

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 C₀, C₁,…, C_n−1 be n distinct copies of C_4m. Denote the vertices of C_4m by x₁, x₂,…, x_4m. Assume the following two labelings of C_4m: f₁:[0, 1, 2, 3, …, 2m−1, 2m+2, 2m+1, 2m+4, 2m+3, …, 4m, 4m−1] and f₂:[4m−1, 0, 1, 2, …., 2m−1, 2m+2, 2m+3, 2m+4, …, 4m] for [x₁, x₂, …, x_4m] 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 C_i. Based upon the strongly odd harmonious labeling of T join corresponding vertices in the distinct copies of C_4m to obtain the graph C_4m ×T. Label the vertices of C_2l with g(x_i) = f₁(x_i)+8m(2l) and the vertices of C_2l−1 with g(x_i) = f₂(x_i)+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(P₂ × P_m)^P_n denote the graph obtained by adding a pendant path P_n to each vertex of P₂ × P_m.

Let P¹, P²,…, P^m be distinct m copies of P_2n+2, the path with 2n+2 vertices. Denote the vertices of P_2n+2 by x₁, x₂,…, x_2n+2. Assume the labeling of P¹ :f₁(x_j) = j − 1, for 1 ≤ j ≤ 2n + 2. Label the vertices of Pⁱ by f(x_j) = (i − 1)(2n + 3) + f₁(x_j ), for 2 ≤ i ≤ m. Now joining the two vertices x_n+1 and x_n+2 in Pⁱ to their correspondences in Pⁱ⁺¹ for 1 ≤ i ≤ m − 1, we get the strongly odd harmonious labeling of (P₂ × P_m)^P_n.

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 [x₁, x₂, …, x_n] and the vertices of P_l by [y₁, y₂, …, y_l]. We construct the strongly odd harmonious labeling of P_l−1 that assigns end vertices labels l − k − 2 and l−2−(l−k−2) = k by lemma 4.2. In the strongly odd harmonious labeling of P_l−1, we join a vertex labeled l−1+k to the end vertex labeled l−k −2 to obtain the odd harmonious labeling of P_l:[l − 1 + k, l − k − 2, …, k]. Label the vertices of G with g, where g(x_i) = f(x_i) + l − 1. Obviously g is (strongly) odd harmonious labeling function.

• Denote the vertices of C_4m by [x₁, x₂, …, x_4m]. Assume the strongly odd harmonious labeling of C_4m: f₁ = [0, 1, 2, …, 2m − 1, 2m + 2, 2m + 1, 2m + 4, 2m + 3, …, 4m, 4m − 1] for [x₁, x₂, …, x_4m]. Remark that f₁ does not assign any vertex the label 2m. Hence in theorem 4.3 by letting G = C_4m the result holds.

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

• The same as the proof of lemma 3.3 by setting T₁ = C_4m ∪ P_n with labeling in corollary 4.4(1) and the result holds immediately.

• Denote the vertices of K_1,t by [x, x₁, x₂, …, x_t], where x is the center vertex. Since K_1,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 K_1,t ∪ P_n 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 K_1,n and K_1,m be two bistars. It is known that K_1,i has only the two odd harmonious labelings f_i : [0, 1, 3, 5, …, 2i−3] and g_i : [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 f_i and g_i. Assume without loss of generality that K_1,n has the labeling f_n : [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 T_n × T_m.

We note here that the graph C_4m ∪ P_n is odd harmonious for all n, m. Actually it is proven in [15] that C_4m∪P_n has an α-labeling, for n ≤ 4m−4 and m ≥ 2, and so is odd harmonious. According to corollary 4.4 the remaining cases are C₈ ∪P₅, C₄ ∪ P₂ and C₄ ∪ P₃. If the vertices of C_4m ∪ P_n are denoted by [x₁, x₂, …, x_4m] ∪ [y₁, y₂, …, y_n], then the odd harmonious labeling of C₈ ∪ P₅, C₄ ∪ P₃ and C₄ ∪ P₂ 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 C₄ ∪ C₄ ∪ C₄ has no α-labeling, but it is odd harmonious. Label the three cycles [5,2,1,0], [8,7,4,15], [10,11,6,3].

Let f be a strongly odd harmonious labeling of G, define the labeling g of the vertices of K_1,t ∪ G in the following manner: g(u) = f(u) if u ∈ V (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 K_1,t with x. Let y = 2m+1−x. Label the vertices of K_1,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 K_1,t is at most 2m+2t−3. Edges in G have labels {1, 3, 5, …, 2m−1} and edges in K_1,t have labels {2m+1, 2m+3, …, 2m+2t−1}.