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.
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 f_{A} : A → {0, 1, …, m − 1} and f_{B} : B → {0, 1, …, m − 1} such that the induced labeling on the edges f_{E}_{(}_{G}_{)} : E(G) → {0, 1, …, m − 1} defined by f_{E}_{(}_{G}_{)}(uv) = f_{A}(u)−f_{B}(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.
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 uv ∈ E(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 f_{A} : A → {0, 1, …, m − 1} and f_{B} : B → {0, 1, …, m − 1} such that the induced labeling on the edges f_{E}_{(}_{G}_{)} : E(G) → {0, 1, …, m − 1} defined by f_{E}_{(}_{G}_{)}(uv) = f_{A}(u) − f_{B}(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 V_{1} = {u ∈ V (G) : f(u) ≤ λ} and V_{2} = {u ∈ V (G) : f(u) > λ}. Define g : V (G) → R by
Then g is a (k, d)-arithmetic vertex function of G and G is (k, d)-arithmetic for all k, d ∈ Z^{+}.
Let [0, 2, 1, 4] be an α-labeling of C_{4}. According to (1.1), the (1, 2)-arithmetic labeling of C_{4} is [−2, 5, −4, 9]. To ensure that vertex labels belong to {0, 1, 2, …, 2m− 1}, We can replace (1.1) with
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 = (x_{1}, y_{1}) is adjacent to v = (x_{2}, y_{2}) whenever [x_{1} = x_{2} and y_{1}y_{2} ∈ E(H)] or [y_{1} = y_{2} and x_{1}x_{2} ∈ E(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 P_{n}.
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 = {u ∈ V (G) : f(u) = 2i, i ≥ 0} and B = {u ∈ V (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 g_{A} and g_{B} as follows: g_{A} : A → {0, 1, …, m − 1}, where ${g}_{A}(u)={\scriptstyle \frac{f(u)}{2}}$ and g_{B} : B → {0, 1, …, m − 1}, where ${g}_{B}(u)=m-1-{\scriptstyle \frac{(f(u)-1)}{2}}$.
It is obvious that both g_{A} and g_{B} are injective.
For each edge uv ∈ E(G) with u ∈ A and v ∈ B we must get g_{B}(v) ≥ g_{A}(u): Assume on contradiction that g_{B}(v) < g_{A}(u). Then $m-1-{\scriptstyle \frac{(f(v)-1)}{2}}<{\scriptstyle \frac{f(u)}{2}}$ and f(u) + f(v) > 2m − 1 a contradiction.
Edge uv, where u ∈ A and v ∈ B, has label ${g}_{B}(v)-{g}_{A}(u)=m-1-{\scriptstyle \frac{(f(v)-1)}{2}}-{\scriptstyle \frac{f(u)}{2}}=m-1-{\scriptstyle \frac{f(u)+f(v)-1}{2}}=m-1-{\scriptstyle \frac{k-1}{2}}$, k = f(u) + f(v). Since 1 ≤ k ≤ 2m − 1, we have $0\le m-1-{\scriptstyle \frac{k-1}{2}}\le m-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 g_{A} : A → {0, 1, .., m − 1} and g_{B} : B → {0, 1, .., m − 1} such that g_{B}(u) ≥ g_{A}(v) for each edge uv with u ∈ B and v ∈ A. Define the odd harmonious labeling function f as follows:
Since both g_{A} and g_{B} are injective, f is injective and f(V (G)) ⊆ {0, 1, …, 2m− 1}.
Edge uv with u ∈ A and v ∈ B has label f(u) + f(v) = 2g_{A}(u) + 2m − 2g_{B}(v) − 1 = 2m − 2(g_{B}(v) − g_{A}(u)) − 1 = 2m − 2k − 1, k = g_{B}(v) − g_{A}(u). Since 0 ≤ k ≤ m − 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 K_{m,m} has a cyclic decomposition into isomorphic copies of G.
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.
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:
It is not difficult to prove that g is an α-labeling for G with characteristic ${\scriptstyle \frac{m}{2}}$ when m even and ${\scriptstyle \frac{m-1}{2}}$ when m odd.
Hence, if G(n, m) is strongly odd harmonious then it decomposes both K_{2}_{m}_{+1} and K_{m,m}.
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.
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:
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 are$\lceil {\scriptstyle \frac{m}{2}}\rceil !\lfloor {\scriptstyle \frac{m}{2}}\rfloor !$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:
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 ${\mathrm{\Pi}}_{i=1}^{m}(2i-1)$, m^{m} 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 T_{1} and T_{2}, let T_{1} △ T_{2} be the tree obtained by identifying a distinguished vertex v^{*} from T_{2} to each vertex of T_{1}. First we prove that T_{1} △ T_{2} is strongly odd harmonious provided that T_{1} and T_{2} are strongly odd harmonious.
Theorem 3.1
If T_{1}and T_{2}are strongly odd harmonious trees, then the graph T_{1} △ T_{2}is strongly odd harmonious.
Proof
Let T_{1} and T_{2} be two strongly odd harmonious trees on n and m vertices, respectively. Let f be a strongly odd harmonious labeling of T_{2} and f′ be the strongly odd harmonious labeling defined by f′(x) = m − 1 − f(x), for x ∈ V (T_{2}). Denote the vertices of T_{2} by x_{0}, x_{1}, …, x_{m}_{−1} such that f(x_{i}) = i. Let T_{0}, T_{1}, …, T^{n}^{−1} be n distinct copies of T_{2} 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_{2} and denote it by ${x}_{j}^{*}$. Let ${x}_{ij}^{*}$ be the corresponding to ${x}_{j}^{*}$ in the copy T^{i}. Based upon the strongly odd harmonious labeling of the tree T_{1}, we adjoin the copy T^{i} of T_{2} to vertex labeled i of T_{1} in such a manner that ${x}_{ij}^{*}$ and the vertex labeled i are identified (See Figure 1). Note that V (T_{1} △ T_{2}) = {x_{01}, x_{02}, …, x_{0(}_{m}_{−1)}} ∪ {x_{11}, x_{12}, …, x_{1(}_{m}_{−1)}} …∪ {x_{(}_{n}_{−1)1}, x_{(}_{n}_{−1)2}, …, x_{(}_{n}_{−1)(}_{m}_{−1)}}. Label the vertices of T_{1}△T_{2} in the following manner:g(x_{0}_{j}) = f(x_{0}_{j}) = f(x_{j}) = j, j = 0, 1, 2, …, m−1, g(x_{ij}) = f(x_{0}_{j}) + im = f(x_{j}) + im = j + im, when i is even and 2 ≤ i ≤ n − 1, g(x_{ij}) = f′(x_{0}_{j})+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_{1}△T_{2} are those either joining the copies T^{i} of T_{2} or an edge in a copy T^{i}. Edge joining T^{i} and T^{j} has label m(i + j + 1) − 1, where i + j is an edge label in T_{1}. Edges in T^{i} 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^{i} 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_{1} and l is an edge label in T_{2} 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_{2} in theorem 3.1 by any other strongly odd harmonious graph, the result still true. Moreover, if we replace the edge ${x}_{ij}^{*}{x}_{kj}^{*}$ in T_{1}△T_{2} with any other edge joining corresponding vertices(other than ${x}_{ij}^{*}$ and ${x}_{kj}^{*}$) in T^{i} and T^{k} we get the generalized T_{1}△T_{2} construction. △_{+1}-construction depends upon making the △-construction on T_{1} – v, where v is the vertex with maximum label in T_{1}, 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 T_{1} = T and T_{2} = P_{2}, the path on two vertices. Let f_{1}, f_{2} be a strongly odd harmonious labelings of T_{1} and T_{2}, respectively. Let x be the vertex in T_{1} with f_{1}(x) = n − 1, where n is the number of vertices of T_{1}. Remove x from T_{1} and construct the generalized (T_{1} − x) △ T_{2} construction in the following manner. Denote the vertices of P_{2} by v_{1} and v_{2}. Assume without any loss of generality that f_{2}(v_{1}) = 0 and f_{2}(v_{2}) = 1. Let T^{0}, T^{1},…, T^{n}^{−2} be n − 1 distinct copies of T_{2} and V (T^{i}) = {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_{1}, we replace the vertex labeled i of T_{1} by the copy T^{i} of T_{2}. Label the vertices of T^{i} with g(v_{0}_{j}) = f_{2}(v_{0}_{j}) = f_{2}(v_{j}) and g(v_{ij}) = f(v_{0}_{j}) + 2i = f_{2}(v_{j}) + 2i. Now we add a vertex u and label it with g(u) = 2n − 2. If f_{1}(N(x)) = {x_{1}, x_{2}, …, x_{k}}, we join the vertex u to {v_{x}_{12}, v_{x}_{22}, …, v_{x}_{k2}}. Denote by u_{i} the vertex labeled i in T_{1}, i = 0, 1, 2, …, n − 2. If u_{i}u_{j} is an edge in T_{1} and d_{T}_{1} (u_{i}, x) = d_{T}_{1} (u_{j}, x) + 1, join v_{i}_{2} to v_{j}_{1}. The resulting graph is T_{1} △_{+1}T_{2}. 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_{2} = P_{2}, this is to make the joining of the copies of T_{2} 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_{1}. Hence g is strongly odd harmonious labeling of S(T) = T_{1}△_{+1}T_{2}.(See Figure 2)
Moreover, if we replace the tree T_{2} = P_{2} 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].
Lemma 3.3
If T_{n} and T_{m} are strongly odd harmonious trees on n and m vertices respectively, then the graph T_{n} × T_{m} is strongly odd harmonious.
Proof
Let f_{1} and f_{2} be strongly odd harmonious labelings of T_{n} and T_{m}, respectively. Denote the vertices of T_{n} by x_{1}, x_{2}, …, x_{n}. Let T^{0}, T^{1}, T^{2}, …, T^{m}^{−1} be m distinct copies of T_{n}. Let V (T^{i}) = {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^{i} 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_{1}(u) = i and f_{1}(v) = j, join the corresponding vertices in T^{i} and T^{j}. Label the vertices of T^{0} with f_{1} and the vertices of T^{i} with g(x_{ij}) = f_{1}(x_{0}_{j}) + 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_{1} 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^{i} have labels {2i(2n−1)+1, 2i(2n−1)+3, …, 2i(2n−1)+2n−3}. Edge labels in between that in T^{i} and T^{i}^{+1}, are the labels assigned to the edges joining T^{l} and T^{s}, where l and s are vertex labels assigned by f_{2} in T_{m} to produce the edge label i + (i + 1), e.g edge labels in between that in T^{1} and T^{2} are labels assigned to the edges joining either T^{0} and T^{3} or T^{1} and T^{2} according to f_{2}, 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_{1}, T_{2} 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 G_{1}(n_{1}, n_{1} − 1) and G_{2}(n_{2}, n_{2} − 1) are a strongly odd harmonious graphs, then the graph G_{1} × G_{2}is strongly odd harmonious.
Lemma 3.5
If T is a strongly odd harmonious tree, then the subdivision graph of T × P_{m} 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×P_{m} as in lemma 3.3, where we assume the strongly odd harmonious labeling of P_{m}, f_{2}(x_{i}) = i−1, for 1 ≤ i ≤ m. Let w_{ij} be the newly added vertices to the edges of T^{i} 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^{0}) with f. Hence f(V (T^{0})) = {0, 2, 4, …, 2n − 2} and f({w_{0}_{j}, 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_{0}_{j}) + 2in.
g(w_{ij}) = 6ni + f(w_{0}_{j}) − 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_{0}_{j}) − 4i = 6n(s+1)−4t−4s−1 and we get f(w_{0}_{j}) = (6n−4)(s−i)+6n−4t−1. We distinguish between two cases:
If i ≤ s: we must have f(w_{0}_{j}) > (6n−4)+6n−4t−1 > 2n−3. Note that f(w_{0}_{j}) ∈ {1, 3, 5, …, 2n − 3} and 1 ≤ t ≤ n.
If i > s: we must have f(w_{0}_{j}) < 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^{i} have labels {8in − 4i + 1, 8in − 4i + 3, …, 8in + 4n − 4i − 5} and edges joining T^{i} and T^{i}^{+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 × P_{m}) is α-labeled.
Proof
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 $\underset{u\in A}{\text{max}}\hspace{0.17em}h(u)={\scriptstyle \frac{g({x}_{(m-1)n})}{2}}=nm-1$ and $\underset{u\in B}{\text{max}}\hspace{0.17em}h(u)=4nm-2(n+m)-{\scriptstyle \frac{g({w}_{(m-1)(n-1)})-1}{2}}=nm$. Hence h is an α-labeling with characteristic nm − 1.
The following lemma generalizes result in [14] that C_{4}_{m}×P_{n} is odd harmonious.
Lemma 3.7
If T is a strongly odd harmonious tree, then the graph C_{4}_{m} × 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 C_{0}, C_{1},…, C_{n}_{−1} be n distinct copies of C_{4}_{m}. Denote the vertices of C_{4}_{m} by x_{1}, x_{2},…, x_{4}_{m}. Assume the following two labelings of C_{4}_{m}: f_{1}:[0, 1, 2, 3, …, 2m−1, 2m+2, 2m+1, 2m+4, 2m+3, …, 4m, 4m−1] and f_{2}:[4m−1, 0, 1, 2, …., 2m−1, 2m+2, 2m+3, 2m+4, …, 4m] for [x_{1}, x_{2}, …, x_{4}_{m}] 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_{4}_{m} to obtain the graph C_{4}_{m} ×T. Label the vertices of C_{2}_{l} with g(x_{i}) = f_{1}(x_{i})+8m(2l) and the vertices of C_{2}_{l}_{−1} with g(x_{i}) = f_{2}(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_{2} × P_{m})^{P}^{n} denote the graph obtained by adding a pendant path P_{n} to each vertex of P_{2} × P_{m}.
Lemma 3.8
All graphs of the form (P_{2} × P_{m})^{P}^{n}are strongly odd harmonious.
Proof
Let P^{1}, P^{2},…, P^{m} be distinct m copies of P_{2}_{n}_{+2}, the path with 2n+2 vertices. Denote the vertices of P_{2}_{n}_{+2} by x_{1}, x_{2},…, x_{2}_{n}_{+2}. Assume the labeling of P^{1} :f_{1}(x_{j}) = j − 1, for 1 ≤ j ≤ 2n + 2. Label the vertices of P^{i} by f(x_{j}) = (i − 1)(2n + 3) + f_{1}(x_{j} ), for 2 ≤ i ≤ m. Now joining the two vertices x_{n}_{+1} and x_{n}_{+2} in P^{i} to their correspondences in P^{i}^{+1} for 1 ≤ i ≤ m − 1, we get the strongly odd harmonious labeling of (P_{2} × P_{m})^{P}^{n}.
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 m ≤ n − 2. Since all odd harmonious graphs on 3 edge are P_{4} and K_{1,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 P_{n} any α-labeling is equivalent to a strongly odd harmonious labeling. It is shown in [1] that:
If 1 ≤ r ≤ n−1, then there exists an α-labeling of P_{2}_{n}_{−1}that assigns the end vertices labels r and r + n.
If 1 ≤ r ≤ n, then there exists an α-labeling of P_{2}_{n} that assigns the end vertices labels r and n − r.
In strongly odd harmonious labeling of P_{n}, we have the following lemma.
Lemma 4.2
If r is even and 1 ≤ r ≤ n − 1, then there exists a strongly odd harmonious labeling of P_{2}_{n}_{−1}that assigns the end vertices labels r and 2n − 2 − r.
If 1 ≤ r ≤ n, then there exists a strongly odd harmonious labeling of P_{2}_{n} 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 G ∪ P_{l} is (strongly) odd harmonious, when l ≥ k + 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 [x_{1}, x_{2}, …, x_{n}] and the vertices of P_{l} by [y_{1}, y_{2}, …, 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.
Corollary 4.4
The graph C_{4}_{m} ∪ P_{n} is strongly odd harmonious for n ≥ 2m + 2.
The graph (C_{4}_{m} × T) ∪ P_{n} is strongly odd harmonious when n ≥ 2m + 2, where T is a strongly odd harmonious tree.
The graph (C_{4}_{m} ∪ P_{n})×T is strongly odd harmonious, where T is a strongly odd harmonious tree, when n ≥ 2m + 2.
The graph K_{1}_{,t} ∪ P_{n} is odd harmonious iff n ≥ 4.
The graph T_{n} ×T_{m} ∪ P_{l} is strongly odd harmonious when l ≥ n+2, where T_{n} and T_{m} are strongly odd harmonious trees on n and m vertices respectively.
Proof
Denote the vertices of C_{4}_{m} by [x_{1}, x_{2}, …, x_{4}_{m}]. Assume the strongly odd harmonious labeling of C_{4}_{m}: f_{1} = [0, 1, 2, …, 2m − 1, 2m + 2, 2m + 1, 2m + 4, 2m + 3, …, 4m, 4m − 1] for [x_{1}, x_{2}, …, x_{4}_{m}]. Remark that f_{1} does not assign any vertex the label 2m. Hence in theorem 4.3 by letting G = C_{4}_{m} the result holds.
By lemma 3.7, the strongly odd harmonious labeling described there not assign the label 2m to any vertex in C_{4}_{m} × T_{n}.
The same as the proof of lemma 3.3 by setting T_{1} = C_{4}_{m} ∪ P_{n} with labeling in corollary 4.4(1) and the result holds immediately.
Denote the vertices of K_{1}_{,t} by [x, x_{1}, x_{2}, …, 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_{4}_{m} ∪ P_{n} is odd harmonious for all n, m. Actually it is proven in [15] that C_{4}_{m}∪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_{8} ∪P_{5}, C_{4} ∪ P_{2} and C_{4} ∪ P_{3}. If the vertices of C_{4}_{m} ∪ P_{n} are denoted by [x_{1}, x_{2}, …, x_{4}_{m}] ∪ [y_{1}, y_{2}, …, y_{n}], then the odd harmonious labeling of C_{8} ∪ P_{5}, C_{4} ∪ P_{3} and C_{4} ∪ P_{2} 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_{4} ∪ C_{4} ∪ C_{4} 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 K_{1}_{,t} ∪ G is odd harmonious.
Proof
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}.
Acknowledgements
The authors would like to thank the anonymous referees for their useful suggestions and comments.
Figures
Fig. 1.T_{1} △ T_{2} with T_{1} is the bistar B_{2,2} and T_{2} is the path on 3 vertices
Fig. 2. The subdivision graph (left) of the bistar B_{2,2} (right)
Abrham, J (1993). Existence theorems for certain types of graceful valuations of snakes. Congr Numer. 93, 17-22.
Acharya, BD, and Hegde, SM (1990). Arithmetic graphs. J Graph Theory. 14, 275-299.
Acharya, BD, and Hegde, SM (1991). On certain vertex valuations of a graph I. Indian J Pure Appl Math. 22, 553-560.
Burzio, M, and Ferrarese, G (1998). The subdivision graph of a graceful tree is a graceful tree. Discrete Math. 181, 275-281.
Gallian, JA (2017). A dynamic survey of graph labeling. Electron J Combin. 20.
Gallian, JA, and Schoenhard, LA (2014). Even harmonious graphs. AKCE Int J Graphs Comb. 11, 27-49.
Gnanajothi, RB 1991. Topics in graph theory. Ph D Thesis. Madurai Kamaraj University.
Koh, KM, Tan, T, and Rogers, DG (1979). Two theorems on graceful trees. Discrete Math. 25, 141-148.
Liadó, A, and Lopez, SC (2005). Edge-decompositions of K_{n,n} into isomorphic copies of a given tree. J Graph Theory. 48, 1-18.
Liang, ZH (2008). On Odd Arithmetic Graphs. J Math Res Exposition. 28, 706-712.
Liang, ZH, and Bai, ZL (2009). On the odd harmonious graphs with applications. J Appl Math Comput. 29, 105-116.
Rosa, A (1966). On certain valuations of the vertices of a graph. Theory Graphs, Int Symp Rome, pp. 349-355
Sarasija, PB, and Binthiya, R (2011). Even harmonious graphs with applications. International journal of computer science and information security. 9, 161-163.
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.
Traetta, T (2013). A complete solution to the two-table Oberwolfach problems. J Combin Theory Ser A. 120, 984-997.