% Template for Electronic Journal of Graph Theory and Applications
% This file must be in the same folder as EJGTAart.sty and EJGTAhead.jpg

\documentclass[12pt]{elsarticle}
\usepackage[left=1in,right=1in, top=1.2in,bottom=1.2in]{geometry}
\usepackage{EJGTAart}
\usepackage{times}
\usepackage{amssymb,amsthm,latexsym,amsmath,epsfig,pgf}
\usepackage{tikz}
\usetikzlibrary{decorations.markings}
\tikzstyle{vertex}=[circle, draw, inner sep=2pt, minimum size=6pt]
\newcommand{\vertex}{\node[vertex]}
\usepackage{pxfonts}
\usepackage{enumitem}
% Set the volume if you know.
\volume{{\bf x} (x)}

% Set the starting page
\firstpage{1}

% Title (or short title) and author name for the header
\runauth{
Semi Arithmetic and Harmonious Labelings
\hspace{2ex} $\arrowvert$\hspace{2ex}
C. Barrientos and M. Z. Youssef}


% Put new theorem or any other settings for your document here
\newtheorem{theorem}{Theorem}[section]
\newtheorem*{theorem A}{Theorem A}
\newtheorem*{theorem B}{N\"olker's Theorem}
\newtheorem{lemma}{Lemma}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{problem}{Problem}
\newtheorem*{question}{Question}
\newtheorem {conjecture}{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}{Remark}[section]
\theoremstyle{remark}
\newtheorem{remarks}{Remarks}
\begin{document}

\begin{frontmatter}
% Write your paper title here
\papertitle{Relaxing the Injectivity Constraint on Arithmetic and Harmonious Labelings}

%% use optional labels to link authors explicitly to addresses. The label may be more than one, use comma to separate

%\author[label1,label]{Edy Tri Baskoro${}^1$}

\author[label1]{Christian Barrientos}
\author[label2]{Maged Z. Youssef}
%\author[label3]{Kiki A. Sugeng}

\address[label1]{\small Department of Mathematics, Valencia College,
Orlando, FL 32832, U.S.A.}
\address[label2]{Department of Mathematics and Statistics, College of Sciences,
 Al Imam Mohammad Ibn Saud Islamic University, Riyadh 11623, Saudi Arabia, and\\
 Department of Mathematics, Faculty of Sciences, Ain Shams University, Cairo 11566, Egypt


\vspace*{2.5ex} 
 {\normalfont chr\_barrientos@yahoo.com, mzyoussef11566@yahoo.com}
 }

\begin{abstract}
Several of the most studied graph labelings are injective functions, this constraint precludes some graphs from admitting such labelings; a well-known example is given by the family of trees that cannot be harmoniously labeled. In order to study the existence of these labelings for certain graphs, the injectivity constraint is often dropped. In this work we eliminate this condition for two different, but related, additive vertex labelings such as the harmonious and arithmetic labelings. The new labelings are called semi harmonious and semi arithmetic. We consider some families of graphs that do not admit the injective versions of these labelings, among the graphs considered here we have cycles and other cycle-related graphs, including the analysis of some operations like the Cartesian product and the vertex or edge amalgamation; in addition, we prove that all trees admit a semi harmonious labeling. Something similar is done with the concept of arithmetic labeling, studying finite unions of semi arithmetic graphs together with some general results.

\let\thefootnote\relax\footnotetext{Received: xx xxxxx 20xx,\quad
  Accepted: xx xxxxx 20xx.\\[3ex]
  }
  
\end{abstract}

\begin{keyword}
% Separate keyword by \sep
semi harmonious \sep semi arithmetic \sep labeling 

% Write the classification number
Mathematics Subject Classification : 05C78

\end{keyword}

\end{frontmatter}

%% Main text
\section{Introduction}

In this work we follow the notation and terminology used in \cite{CL} and \cite{Ga}. The set of integers is denoted by $\mathbb{Z}$ while the set of nonnegative integers is denoted by $\mathbb{N}$ and the additive group of integers (mod $n$) by $\mathbb{Z}_n$. The arithmetic sequence of length $q$ with first element $a$ and difference $d$ is denoted by $[a, a+(q-1)d]_d$, except when $d=1$, where we do not use the subindex. By a ($p, q$)-graph we understand a graph with $p$ vertices and $q$ edges, i.e., a graph of order $p$ and size $q$.

An \emph{additive vertex labeling} of a ($p, q$)-graph $G$ is a function $f:V(G) \rightarrow S$, where $S$ is a set of nonnegative integers, that induces for each edge $uv$ of $G$ a \emph{weight} defined as $f(u)+f(v)$. In this work, the word labeling is used in the context of an additive vertex labeling. In \cite{925}, Graham and Sloane introduced the concept of harmonious labeling to study modular versions of additive bases problems stemming from error-correcting codes; these labelings are one of the most study additive vertex labelings. Let $G$ be a ($p, q$)-graph such that $q \geq p$ and $f$ be a labeling of $G$, we say that $f$ and $G$ are \emph{harmonious} if $f$ is an injective function with codomain $\mathbb{Z}_q$, and the set of induced weights is $\mathbb{Z}_q$, after each weight has been reduced (mod $q$). Let $w_1, w_2, \dots, w_q$ be consecutive integers, then $\{w_1, w_2, \dots, w_q\} \equiv \mathbb{Z}_q$ modulo $q$. Therefore, assuming that $f:V(G) \rightarrow \mathbb{Z}_q$ is injective and the induced weights form a set of $q$ consecutive integers, then $f$ is harmonious. Trees constitute an important family of graphs that fail the condition $q \geq p$. This type of graph was also considered in \cite{925}; there, Graham and Sloane dropped the injectivity condition allowing one label to be used twice. In this work we allow multiple repetitions of multiple labels. The following result was proved in \cite{925}, we included it here because it is used in some of the results in Section 2.

\begin{theorem}
If $G$ is a harmonious graph of even size $q$ where the degree of every vertex is divisible by $2^k$, for some positive integer $k$, then $q$ is divisible by $2^{k+1}$.
\end{theorem}

The following result, due to Youssef \cite{2873}, proves the existence of a harmonious labeling for graphs obtained with multiple copies of the same harmonious graph. By $nG$ we understand the disjoint union of $n$ copies of a graph $G$ and by $G^{(n)}$, the one-point union of $n$ copies of $G$.

\begin{theorem}
If $G$ is a harmonious graph, then both $nG$ and $G^{(n)}$ are harmonious provided that $n$ is a positive odd integer.
\end{theorem}

Some variations of the concept of harmonious labeling have been studied by several authors. Lee et al. \cite{1532} generalized the concept of harmonious graph in the following terms: a graph $G$ with $q$ edges is called \emph{felicitous} if there exists an injective function $f:V(G) \rightarrow \mathbb{Z}_{q+1}$ such that the set of induced weights is $\mathbb{Z}_q$, when each weight is reduced (mod $q$). Among other results, they proved that the cycle $C_n$ is felicitous if and only if $n \not \equiv 2(\text{mod } 4)$. Chang et al. \cite{558} said that a graph $G$ with $q$ edges is \emph {strongly k-harmonious} if there exists an injective function $f:V(G) \rightarrow \mathbb{Z}_q$ such that the set of induced weights is $[k, k+q-1]$. A little less restrictive is the concept of ($k, d$)-arithmetic graph introduced by Acharya and Hegde \cite{39}; a graph $G$ with $q$ edges is called \emph{($k, d$)-arithmetic} if there exists an injective function $f:V(G) \rightarrow \mathbb{N}$ such that the set of induced weights is $[k, k+(q-1)d]_d$ for two positive integers $k$ and $d$. Lourdsamy and  Seenivasan \cite{1656} said that a graph $G$ with $q$ edges is \emph{vertex equitable} if there exists a function $f:V(G) \rightarrow [0, \lceil \frac{q}{2} \rceil ]$ such that the set of induced weights is $[1, q]$ and for every pair of elements $i$ and $j$ in the range of $f$, the number of vertices labeled $i$ and the number of vertices labeled $j$ differ by at most one unit. They characterized the cycles that are vertex equitable.

In this work we generalize the concepts of harmonious and $(k, d)$-arithmetic graphs by relaxing the injectivity constraint of the corresponding labeling. We refer to the new versions of these labelings as semi harmonious and semi $(k, d)$-arithmetic. In Section 2 we show the existence of a semi harmonious labeling for several types of cycle-related graphs; we characterize the cycles that admit such a labeling; using semi harmonious cycles we study the finite union, the one-point union, the edge amalgamation, and the Cartesian product with the path $P_m$. We conclude that section proving that the complete bipartite graph is semi harmonious as well. We continue in Section 3 proving that all trees are semi harmonious. In Section 4 we study semi $(k, d)$-arithmetic labelings, we prove that if $G$ is semi $(k, d)$-arithmetic, then it is also semi $(rk, rd)$-arithmetic for every $r \geq 1$ and that $nG$ is both semi $(k, d)$-arithmetic and semi $(k+d, d)$-arithmetic; we also study the complete bipartite graph proving that any graph which components are complete bipartite graphs is semi $(k, d)$-arithmetic for any ordered pair $(k, d)$ of positive integers; in the last result of this section we prove that if $G_i$ is a semi $(k_i, d)$-arithmetic graph of size $q_i$ for each $i=1,2$, then $G_1 \cup G_2$ is semi $(k_1, d)$-arithmetic.



\section{Semi Harmonious Labelings}

A $(p, q)$-graph $G$ is said to be \emph{semi harmonious} if there exists a labeling $f:V(G) \rightarrow \mathbb{Z}_q$ such that $\{(f(u)+f(v))(\text{mod } q): uv \in E(G)\}=\mathbb{Z}_q$. Every labeling $f$ that satisfies this definition is called \emph{semi harmonious}.

Suppose that $f$ is a semi harmonious labeling of a ($p, q$)-graph $G$. Let $c$ be a positive constant, we said that the labeling $g$ of $G$ is a \emph{shifting} of $f$ in $c$ units if $g(u)=f(u)+c$, for every $u \in V(G)$. It is important to note that if $uv$ is the edge of $G$ of weight $m$, then $g(u) + g(v) = m + 2c$; in other terms, the set of edge labels induced by $g$ consists of $q$ consecutive integers.

Note that the necessary condition for the existence of a harmonious labeling for a graph of even size, given in Theorem 1.1, is still valid for semi harmonious labelings. In addition we have that for every $n \geq 3$, the complete graph $K_n$ is semi harmonious if and only if $K_n$ is harmonious. While the cycle $C_n$ is harmonious if and only if $n$ is odd, we can prove that the cycle $C_n$  is semi harmonious except when $n \equiv 2(\text{mod } 4)$. The structure of the proof is similar to the proofs in \cite{Fau} and \cite{1656} for the corresponding labelings.

\begin{theorem}
The cycle $C_n$ is semi harmonious if and only if $n \not \equiv 2(\text{mod } 4)$.
\end{theorem}

\begin{proof}
The necessity follows from Theorem 1.1. To prove the sufficiency, we analyze two cases, in either case we assume that $V(G) = \{u_1, u_2, \dots, u_n\}$ and $E(G) = \{u_1u_2, u_2u_3, \dots, u_nu_1\}$.

\textbf{Case 1:} When $n \equiv 0 \text{ or } 3 (\text{mod } 4)$. Consider the labeling $f : V(G) \rightarrow \mathbb{Z}_n$ defined for every vertex $u_i$ of $C_n$ as follows:

\[
f(u_i) = \begin{cases}
\frac{i}{2} & \text{if } i \text{ is even}, \\
\frac{i-1}{2} & \text{if } i \leq \frac{n}{2} \text{ is odd}, \\
\frac{i+1}{2} & \text{if } i > \frac{n}{2} \text{ is odd}.
\end{cases}
\]
Observe that the range of $f$ is $\big [0, \frac{n}{2} \big ]$ when $n$ is even and $\big[0, \frac{n+1}{2}\big]$ when $n$ is odd. Now we want to determine the weight of the edge $u_iu_{i+1}$, that is, $f(u_i)+f(u_{i+1})$. Let $i < \big\lceil \frac{n}{2} \big \rceil$; if $i$ is even, then $f(u_i)+f(u_{i+1})=\frac{i}{2}+\frac{i}{2}=i$; if $i$ is odd, then $f(u_i)+f(u_{i+1})=\frac{i-1}{2}+\frac{i+1}{2}=i$. Therefore, we have $\big\lfloor \frac{n-1}{2} \big\rfloor$ edges which weights are $1, 2, \dots, \big\lfloor \frac{n-1}{2} \big\rfloor$. Suppose now that $\big\lceil \frac{n}{2} \big\rceil \leq i < n$; if $i$ is even, then $f(u_i)+f(u_{i+1})=\frac{i}{2}+\frac{i+2}{2}=i+1$; if $i$ is odd, then $f(u_i)+f(u_{i+1})=\frac{i+1}{2}+\frac{i+1}{2}=i+1$. Thus, we have $\big\lfloor \frac{n}{2} \big\rfloor$ edges which weights are $\big\lceil \frac{n}{2} \big\rceil+1, \big\lceil \frac{n}{2} \big\rceil+2, \dots, n$. Since the edge $v_nv_1$ has weight $f(u_n)+f(u_{1})=\big\lceil \frac{n}{2} \big\rceil + 0 = \big\lceil \frac{n}{2} \big\rceil$, the set of weights induced by $f$ is $\{1, 2, \dots, n\}$. Consequently, $f$ is semi harmonious.


\textbf{Case 2:} When $n \equiv 1 (\text{mod } 4)$. In this case the labeling $f$ is defined as:
\[
f(u_i) = \begin{cases}
\frac{i-2}{2} & \text{if } i \text{ is even}, \\
\frac{i-1}{2} & \text{if } i \leq \frac{n+1}{2} \text{ is odd}, \\
\frac{i+1}{2} & \text{if } i\geq \frac{n+3}{2} \text{ is odd}.
\end{cases}
\]
Now, the range of $f$ is $\big[0, \frac{n+1}{2}\big]$. Suppose that $1 \leq i \leq \frac{n+1}{2}$; if $i$ is odd, then $f(u_i)+f(u_{i+1})=\frac{i-1}{2}+\frac{i+1-2}{2}=i-1$; if $i$ is even, then $f(u_i)+f(u_{i+1})=\frac{i-2}{2}+\frac{i+1-1}{2}=i-1$. Thus, we get $\frac{n+1}{2}$ edges which weights are $0, 1, \dots, \frac{n-1}{2}$. Assuming that $\frac{n+3}{2} \leq i \leq n-1$, the weight of $u_iu_{i+1}$ is $f(u_i)+f(u_{i+1})=\frac{i-2}{2}+\frac{i+2}{2}=i$ when $i$ is even and $f(u_i)+f(u_{i+1})=\frac{i+1}{2}+\frac{i+1-2}{2}=i$ when $i$ is odd. Thus, we get $\frac{n-3}{2}$ edges which weights are $\frac{n+3}{2}, \frac{n+5}{2}, \dots, n-1$. The edge $u_nu_1$ has weight $\frac{n+1}{2}+0=\frac{n+1}{2}$. Hence, the set of edge labels is $\mathbb{Z}_n$. Therefore, $f$ is a semi harmonious labeling of $C_n$.
\end{proof}

We show in Figure 1 three examples of the semi harmonious labeling of $C_n$ described within the proof of Theorem 2.1 corresponding to the congruences of $n$ (mod 4).

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[xscale=0.5,yscale=0.5]

\vertex [fill] (1) at (3,7) [label=above:{0}]{};
\vertex [fill] (2) at (1.35,6.5) [label=above left:{1}]{};
\vertex [fill] (3) at (0.25,5.25) [label=left:{1}]{};
\vertex [fill] (4) at (0.1,3.55) [label=left:{2}]{};
\vertex [fill] (5) at (0.75,2) [label=below left:{2}]{};
\vertex [fill] (6) at (2.2,1.2) [label=below:{3}]{};
\vertex [fill] (7) at (3.8,1.2) [label=below:{4}]{};
\vertex [fill] (8) at (5.25,2) [label=below right:{4}]{};
\vertex [fill] (9) at (5.9,3.55) [label=right:{5}]{};
\vertex [fill] (10) at (5.75,5.25) [label=right:{5}]{};
\vertex [fill] (11) at (4.65,6.5) [label=above right:{6}]{};
\draw[thick]	(1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) --(8) -- (9) -- (10) -- (11) --(1);

\vertex [fill] (1) at (12,7) [label=above:{0}]{};
\vertex [fill] (2) at (10.5,6.6) [label=above left:{1}]{};
\vertex [fill] (3) at (9.4,5.5) [label=above left:{1}]{};
\vertex [fill] (4) at (9,4) [label=left:{2}]{};
\vertex [fill] (5) at (9.4,2.5) [label=below left:{2}]{};
\vertex [fill] (6) at (10.5,1.5) [label=below left:{3}]{};
\vertex [fill] (8) at (13.5,1.5) [label=below right:{4}]{};
\vertex [fill] (9) at (14.6,2.5) [label=below right:{5}]{};
\vertex [fill] (10) at (15,4) [label=right:{5}]{};
\vertex [fill] (11) at (14.6,5.5) [label=above right:{6}]{};
\vertex [fill] (12) at (13.5,6.6) [label=above right:{6}]{};
\vertex [fill] (7) at (12,1) [label=below:{4}]{};
\draw[thick]	(1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) --(8) -- (9) -- (10) -- (11) -- (12) --(1);

\vertex [fill] (1) at (21,7) [label=above:{0}]{};
\vertex [fill] (2) at (19.65,6.7) [label=above left:{0}]{};
\vertex [fill] (3) at (18.6,5.75) [label=left:{1}]{};
\vertex [fill] (4) at (18.05,4.35) [label=left:{1}]{};
\vertex [fill] (5) at (18.2,2.95) [label=left:{2}]{};
\vertex [fill] (6) at (19,1.8) [label=below left:{2}]{};
\vertex [fill] (7) at (20.25,1.15) [label=below:{3}]{};
\vertex [fill] (8) at (21.75,1.15) [label=below:{3}]{};
\vertex [fill] (9) at (23,1.8) [label=below right:{5}]{};
\vertex [fill] (10) at (23.8,2.95) [label=right:{4}]{};
\vertex [fill] (11) at (23.95,4.35) [label=right:{6}]{};
\vertex [fill] (12) at (23.4,5.75) [label=right:{5}]{};
\vertex [fill] (13) at (22.35,6.7) [label=above right:{7}]{};
\draw[thick]	(1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) --(8) -- (9) -- (10) -- (11) -- (12) -- (13) -- (1);

\end{tikzpicture}
\caption{Semi harmonious labeling of $C_{11}$, $C_{12}$, and $C_{13}$}
\end{center}
\end{figure}

\begin{theorem}
Suppose that for each $i \in \{1, 2, \dots, s\}$, the cycle $C_{n_i}$ is semi harmonious. For each $k \in \{0, 1, 3\}$, we define the super set $S_k=\{C_{n_i}: n_i \equiv k (\text{mod } 4)\}$, where  If $|S_3| - |S_1|$ is either 0 or 1, then the 2-regular graph $G=\cup_{i=1}^sC_{n_i}$ is semi harmonious.
\end{theorem}

\begin{proof}
If $G$ is connected, then $G$ is semi harmonious as was proven in Theorem 2.1. Assume that $G$ is disconnected; we arrange the components of $G$ in such a way that for each $1 \leq j \leq r$, $n_j \equiv 0(\text{mod } 4)$, and for each $r+1 \leq j < s$, whenever $n_j \equiv 3(\text{mod } 4)$ then $n_{j+1} \equiv 1(\text{mod } 4)$. Thus, if $|S_3|=|S_1|$, then the size of $G$ is divisible by 4 and when $|S_3|=|S_1|+1$, the size of $G$ is congruent to 3(mod 4) and $n_s \equiv 3(\text{mod } 4)$. Each component of $G$ is initially labeled using the corresponding semi harmonious labeling in Theorem 2.1. Most of these initial labelings will be shifted; thus, the shifted labeling will be the final labeling of that component.

Suppose that $1 \leq j \leq r$; when $j=1$, the final labeling of $C_{n_1}$ is its initial labeling; for $j > 1$, the final labeling of $C_{n_j}$ is obtained by shifting its initial labeling $\frac{1}{2} \sum_{i=1}^{j-1}n_i$ units. Since $n_j \equiv 0(\text{mod } 4)$ for each $1 \leq j \leq r$, the initial labeling of $C_{n_j}$ induces the weights $1, 2, \dots, n_j$; therefore, its final labeling induces the weights $1+\sum_{i=1}^{j-1}n_i, 2+\sum_{i=1}^{j-1}n_i, \dots, n_j+\sum_{i=1}^{j-1}n_i =\sum_{i=1}^{j}n_i$. Thus, the weights on the edges of $\cup_{i=1}^rC_{n_i}$ are $1, 2, \dots, \sum_{i=1}^{r}n_i$. Note that $\sum_{i=1}^{r}n_i$ is an even number.

Suppose now that $j > r$; the final labeling of $C_{n_j}$ is obtained in essentially the same way, but the shifting applied to the initial labeling of $C_{n_j}$ depends of the parity of $\sum_{i=1}^{j-1}n_i$. We start with $j=r+1$, since $\sum_{i=1}^{r}n_i$ is an even number and the initial labeling of $C_{n_{r+1}}$ induces the weights $1, 2, \dots, n_{r+1}$, where $n_{r+1}$ is odd, shifting it $\frac{1}{2}\sum_{i=1}^{r}n_i$ units, induces the weights $1, 2, \dots, \sum_{i=1}^{r+1}n_i$ on the edges of $\cup_{i=1}^{r+1}C_{n_i}$, but now $\sum_{i=1}^{r+1}n_i$ is odd, however the initial labeling of $C_{n_{r+2}}$ induces the weights $0, 1, \dots, n_{r+2}-1$; consequently, if it is shifted $\frac{1}{2}\big(1+\sum_{i=1}^{r+1}n_i\big)$ units, the induced weights on the edges of $\cup_{i=1}^{r+2}C_{n_i}$ are $1, 2, \dots, \sum_{i=1}^{r+2}n_i$, where $\sum_{i=1}^{r+2}n_i$ is an even number. We continue with this process until each component has its final labeling. The process guarantees that the induced weights on the edges of $G$ are $1, 2, \dots, \sum_{i=1}^{s}n_i$. In other terms, the final labeling of $G$ is semi harmonious.
\end{proof}

In Figure 2 we show an example of this labeling where $G=3C_4 \cup C_8 \cup C_7 \cup C_5$.\\

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[xscale=1.0,yscale=1.0]

\vertex [fill](1) at (0,1) [label=left :{0}]{};
\vertex [fill](2) at (0,0) [label=left:{1}]{};
\vertex [fill](3) at (1,1) [label=right:{2}]{};
\vertex [fill](4) at (1,0) [label=right:{2}]{};
\draw[thick]	(1) -- (2) -- (4) -- (3) -- (1);
\vertex [fill](1) at (2.5,1) [label=left :{2}]{};
\vertex [fill](2) at (2.5,0) [label=left:{3}]{};
\vertex [fill](3) at (3.5,1) [label=right:{4}]{};
\vertex [fill](4) at (3.5,0) [label=right:{4}]{};
\draw[thick]	(1) -- (2) -- (4) -- (3) -- (1);
\vertex [fill](1) at (5,1) [label=left :{4}]{};
\vertex [fill](2) at (5,0) [label=left:{5}]{};
\vertex [fill](3) at (6,1) [label=right:{6}]{};
\vertex [fill](4) at (6,0) [label=right:{6}]{};
\draw[thick]	(1) -- (2) -- (4) -- (3) -- (1);
\vertex [fill](1) at (7.5,3) [label=left :{6}]{};
\vertex [fill](2) at (7.5,2) [label=left:{7}]{};
\vertex [fill](3) at (7.5,1) [label=left :{7}]{};
\vertex [fill](4) at (7.5,0) [label=left:{8}]{};
\vertex [fill](5) at (8.5,3) [label=right :{10}]{};
\vertex [fill](6) at (8.5,2) [label=right:{10}]{};
\vertex [fill](7) at (8.5,1) [label=right :{9}]{};
\vertex [fill](8) at (8.5,0) [label=right:{9}]{};
\draw[thick]	(1) -- (2) -- (3) -- (4) -- (8) -- (7) -- (6) -- (5) -- (1);
\vertex [fill](1) at (10.5,3) [label=left :{10}]{};
\vertex [fill](2) at (10,2) [label=left:{11}]{};
\vertex [fill](3) at (10,1) [label=left :{11}]{};
\vertex [fill](4) at (10,0) [label=left:{12}]{};
\vertex [fill](5) at (11,2) [label=right:{14}]{};
\vertex [fill](6) at (11,1) [label=right :{13}]{};
\vertex [fill](7) at (11,0) [label=right:{13}]{};
\draw[thick]	(1) -- (2) -- (3) -- (4) -- (7) -- (6) -- (5) -- (1);
\vertex [fill](0) at (13,2) [label=left :{14}]{};
\vertex [fill](1) at (12.5,1) [label=left :{14}]{};
\vertex [fill](2) at (12.5,0) [label=left:{15}]{};
\vertex [fill](3) at (13.5,1) [label=right:{17}]{};
\vertex [fill](4) at (13.5,0) [label=right:{15}]{};
\draw[thick]	(0) -- (1) -- (2) -- (4) -- (3) -- (0);

\end{tikzpicture}
\caption{Semi harmonious labeling of a 2-regular graph with six components}
\end{center}
\end{figure}


If $F$ and $G$ are connected graphs, a \emph{one-point union} of them is any of the graphs obtained by amalgamating a vertex of $F$ with a vertex of $G$; when $F$ and $G$ are vertex transitive, the outcome of the one-point union is unique. An immediate consequence of Theorem 2.1 is that the one-point union of $C_m$ with $C_n$ is semi harmonious when both cycles are semi harmonious and $m+n \not \equiv 2(\text{mod } 4)$. We prove this claim in the following corollary.

\begin{corollary}
Let $C_m$ and $C_n$ be semi harmonious. If $m+n \not \equiv 2(\text{mod } 4)$, then the one-point union of $C_m$ with $C_n$ is a semi harmonious graph.
\end{corollary}

\begin{proof}
Suppose that the cycles $C_m$ and $C_n$ are semi harmonious and that $m+n \not \equiv 2(\text{mod } 4)$. We assume that both cycles are labeled using the function $f$ described in Theorem 2.1. We analyze three cases determined by the equivalence class of  $m+n$ (mod 4). 

\textbf{Case 1:} When $m+n \equiv 0(\text{mod } 4)$. In this case, either $m,n \equiv 0(\text{mod } 4)$ or $m \equiv 3(\text{mod } 4)$ and $n \equiv 1(\text{mod } 4)$. Suppose first that $m,n \equiv 0(\text{mod } 4)$, then the largest label used on $C_m$ is $\frac{m}{2}$; the initial labeling of $C_n$ is shifted $\frac{m}{2}$ units, thus the labels on this cycle are in the range $\big[\frac{m}{2}, \frac{m+n}{2}\big]$ and the induced weights are in $[m+1, m+n]$. Since both cycles have a vertex labeled $\frac{m}{2}$, we amalgamate them to produce the one-point union which is semi harmonious. Suppose now that $m \equiv 3(\text{mod } 4)$ and $n \equiv 1(\text{mod } 4)$; the labeling of $C_n$ is shifted $\frac{m+1}{2}$ units, 
the labels on $C_n$ are in the range $\big[\frac{m+1}{2}, \frac{m+n+2}{2}\big]$ and the induced weights are in $[m+1, m+n]$. Amalgamating the vertices labeled $\frac{m+1}{2}$ we get the one-point union of these cycles together with a semi harmonious labeling.

\textbf{Case 2:} When $m \equiv 0(\text{mod } 4)$ and $n \equiv 3(\text{mod } 4)$. As we did before, the labeling of $C_n$ is shifted $\frac{m}{2}$ units; in this way the labels on $C_n$ are in the range $\big[\frac{m}{2}, \frac{m+n+1}{2}\big]$ and the induced weights are in $[m+1, m+n]$. We proceed with the amalgamation of a vertex of $C_m$ labeled $\frac{m}{2}$ with the vertex of $C_n$ with this label. The resulting graph is semi harmonious.

\textbf{Case 3:}  When $m \equiv 1(\text{mod } 4)$ and $n \equiv 0(\text{mod } 4)$.  The largest label used on $C_m$ is $\frac{m+1}{2}$, so the labeling of $C_n$ is shifted $\frac{m+1}{2}-1=\frac{m-1}{2}$ units, then the labels on $C_n$ are in the range $\big[\frac{m-1}{2}, \frac{m+n-1}{2}\big]$ and the induced weights are in $[m, m+n-1]$. Since the weights on the edges of $C_m$ are in $[0, m-1]$, the amalgamation of these labeled cycles, using the vertex labeled $\frac{m+1}{2}$ in $C_m$ with one of the vertices labeled $\frac{m+1}{2}$ in $C_n$, results in the one-point union with the appropriate  semi harmonious labeling.
\end{proof}

The labeling of $C_n$ given in Theorem 2.1 can be also used to produce a semi harmonious labeling of a subfamily of outerplanar graphs. This subfamily is obtained via edge amalgamation of two cycles, say $C_m$ and $C_n$, where both $m$ and $n$ are odd or $m$ is odd and $n \equiv 0(\text{mod } 4)$. The edge amalgamation of $C_m$ and $C_n$ is designated with the symbol $C_m \boxbar C_n$. In order to present a broader spectrum of semi harmonious graphs that  can be built with the labelings in Theorem 2.1, we need to introduce another semi harmonious labeling for the case where $m \equiv 1(\text{mod } 4)$. We present this labeling in the following lemma; since the proof is basically the same that the proof of Theorem 2.1 we omit some details but include the most significant steps. 

\begin{lemma}
The cycle $C_m$ is semi harmonious when $m \equiv 1(\text{mod } 4)$.
\end{lemma}

\begin{proof}
Consider the following labeling of the vertices of $C_m$:
\[
f(u_i) = \begin{cases}
i-1 & \text{if } 1 \leq i \leq \frac{m+1}{2} \text{ is odd}, \\
i-2 & \text{if } 2 \leq i \leq \frac{m-1}{2} \text{ is even}, \\
m+1-i & \text{if } i \geq \frac{m+3}{2}.
\end{cases}
\]
The range of $f$ is $\big[0, \frac{m-1}{2}\big]$. If $2 \leq i \leq \frac{m+1}{2}$, the edge $u_iu_{i-1}$ has weight $2i-4$ independently of the parity of $i$. If $\frac{m+3}{2} \leq i \leq m$, the edge $u_iu_{i+1}$ (understanding that $m+1 \equiv 1(\text{mod } n)$) has weight $2(m-i)+1$. The edge $u_{\frac{m+1}{2}}u_{\frac{m+3}{2}}$ has weight $m-1$. Therefore, the set of induced weights is $[0, m-1]$; consequently, $f$ is a semi harmonious labeling of $C_m$.
\end{proof}

\begin{theorem}
The edge amalgamation $C_m \boxbar C_n$ is a semi harmonious graph when any of the following conditions holds:
\begin{enumerate}[label=(\arabic*)]
	\item $m \equiv 3(\text{mod } 4)$ and $n \equiv 0(\text{mod } 4)$ or $n \equiv 3(\text{mod } 4)$,
	\item $m \equiv 1(\text{mod } 4)$ and $n \equiv 0(\text{mod } 4)$ or $n \equiv 1(\text{mod } 4)$.
\end{enumerate}
\end{theorem}

\begin{proof}
Suppose that $m \equiv 3(\text{mod } 4)$ and $n \equiv 0(\text{mod } 4)$ or $n \equiv 3(\text{mod } 4)$. We use on both cycles the labeling described in Theorem 2.1, but shifting $\frac{m-1}{2}$ units the labeling of $C_n$; in this way both cycles have an edge with end-vertices labeled $\frac{m-1}{2}$ and $\frac{m+1}{2}$. The labels on $C_m$ are in the range $\big[0, \frac{m+1}{2}\big]$ and the induced weights are in $[1, m]$; the labels on $C_n$ are in the range $\big[\frac{m-1}{2}, \frac{m+n-1}{2}\big]$ when $n$ is even or $\big[\frac{m-1}{2}, \frac{m+n}{2}\big]$ when $n$ is odd; the weights on the edges of $C_n$ are in $[m, m+n-1]$. Amalgamating the edges of weight $m$ we obtain $C_m \boxbar C_n$ with a semi harmonious labeling.

Suppose now that $m \equiv 1(\text{mod } 4)$ and $n \equiv 0(\text{mod } 4)$ or $n \equiv 1(\text{mod } 4)$. If $m$ and $n$ are both odd, the initial labeling of $C_m$ and $C_n$ is the labeling in Lemma 2.1; we shift $\frac{n-1}{2}$ units the labeling of $C_m$, in this way the labels on $C_m$ are in the range $\big[\frac{n-1}{2}, \frac{m+n-2}{2}\big]$ and the induced weights are in $[n-1, m+n-2]$. The vertices $u_1$ and $u_2$ of $C_m$ are now labeled $\frac{n-1}{2}$. Since the labeling of $C_n$ has not been modified, the vertices $u_{\frac{n+1}{2}}$ and $u_{\frac{n+3}{2}}$ are labeled $\frac{n-1}{2}$. Then, both cycles have an edge of weight $n-1$ which end-vertices are labeled $\frac{n-1}{2}$. Amalgamating these edges we obtain $C_m \boxbar C_n$ with a semi harmonious labeling. If $m$ and $n$ have different parity, the labeling of $C_m$ is coming from Lemma 2.1 and the labeling of $C_n$ from Theorem 2.1; we shift $\frac{n}{2}$ units the labeling of $C_m$, in this way the labels on $C_m$ are in the range $\big[\frac{n}{2}, \frac{m+n-1}{2}\big]$ and the induced weights are in $[n, m+n-1]$. The vertices $u_1$ and $u_2$ of $C_m$ are labeled $\frac{n}{2}$, this is also the label on the vertices $n_{n-1}$ and $u_n$ of $C_n$. Thus, both cycles have an edge of weight $n$ which end-vertices are labeled $\frac{n}{2}$. The amalgamation of these edges produces $C_m \boxbar C_n$ with a semi harmonious labeling.
\end{proof}

In the next result we work with the Cartesian product of any of the semi harmonious cycles and a path, proving that $C_n \times P_2$ is semi harmonious except when $n \equiv 2(\text{mod } 4)$.

\begin{lemma}
If $C_n$ is semi harmonious, then the Cartesian product of $C_n$ and $P_2$ is a semi harmonious graph.
\end{lemma}

\begin{proof}
When $n \equiv 0, 3(\text{mod } 4)$, we use on $C_n$ the labeling described in Theorem 2.1; when $n \equiv 1(\text{mod } 4)$, we use on $C_n$ the labeling described in Lemma 2.1. Since $C_n \times P_2$ contains two copies of $C_n$, we label both copies with its corresponding semi harmonious labeling and shift the labels on the second copy $n$ units. When $n \equiv 0, 3(\text{mod } 4)$, the labels on the first copy of $C_n$ are in $\big[0, \big\lceil \frac{n}{2} \big\rceil \big]$ with induced weights in $[1, n]$ and on the second copy the labels are in $\big[n, n+\big\lceil \frac{n}{2} \big\rceil \big]$ with induced weights in $[2n+1, 3n]$. When $n \equiv 1(\text{mod } 4)$, the labels of the first copy are in $\big[0, \frac{n-1}{2}\big]$ and the induced weights in $[0, n-1]$, the labels of the second copy are in $\big[n, \frac{3n-1}{2}\big]$ and the weights in $[2n, 3n-1]$.

Independently of the value of $n$, the Cartesian product $C_n \times P_2$ is obtained by connecting $u_i^1$ with $u_{i+1}^2$, where the sum $i+1$ is taken mod $n$.

\textbf{Case 1:} When $n \equiv 0 (\text{mod } 4)$. Suppose that $1 \leq i \leq \frac{n-2}{2}$; if $i$ is odd, then the edge $u_i^1u_{i+1}^2$ has weight $\frac{i-1}{2}+\frac{i+1}{2}+n=n+i$; if $i$ is even, this edge has weight $\frac{i}{2}+\frac{i+1-1}{2}+n=n+i$. Thus, we have $\frac{n-2}{2}$ edges whose weights are $n+1, n+2, \dots, n+ \frac{n-2}{2}=\frac{3n-2}{2}$. The edge $u_n^1u_1^2$ has weight $n+ \frac{n}{2} =\frac{3n}{2}$. Suppose now that $ \frac{n}{2} \leq i \leq n-1$; if $i$ is odd, then the edge $u_i^1u_{i+1}^2$ has weight $\frac{i+1}{2}+\frac{i+1}{2}+n=n+i+1$; if $i$ is even, this edge has weight $\frac{i}{2}+\frac{i+1+1}{2}+n=n+i+1$. Thus, we have $\frac{n}{2}$ edges which weights are $\frac{3n}{2}+1, \frac{3n}{2}+2, \dots, 2n$. Therefore, the weights of the edges of $C_n \times P_2$ are the integers in $[1, 3n]$; i.e., this graph is semi harmonious when $n \equiv 0(\text{mod } 4)$.

\textbf{Case 2:} When $n \equiv 3 (\text{mod } 4)$. Suppose that $1 \leq i \leq \frac{n-1}{2}$; if $i$ is odd, then the edge $u_i^1u_{i+1}^2$ has weight $\frac{i-1}{2}+\frac{i+1}{2}+n=n+i$; if $i$ is even, this edge has weight $\frac{i}{2}+\frac{i+1-1}{2}+n=n+i$. Thus, we have $\frac{n-1}{2}$ edges whose weights are $n+1, n+2, \dots, \frac{3n-1}{2}$. The edge $u_n^1u_1^2$ has weight $\frac{n+1}{2}+n=\frac{3n+1}{2}$. Suppose now that $\frac{n+1}{2}\leq i \leq n-1$; if $i$ is odd, then the edge $u_i^1u_{i+1}^2$ has weight $\frac{i+1}{2}+\frac{i+1}{2}+n=n+i+1$; if $i$ is even, this edge has weight $\frac{i}{2}+\frac{i+1+1}{2}+n=n+i+1$. Thus, we have $\frac{n-1}{2}$ edges which weights are $\frac{3n+1}{2}+1, \frac{3n+1}{2}+2, \dots, 2n$. Therefore, the weights of the edges of $C_n \times P_2$ are the integers in $[1, 3n]$; i.e., this graph is semi harmonious when $n \equiv 3(\text{mod } 4)$.

\textbf{Case 3:} When $n \equiv 1 (\text{mod } 4)$. Suppose that $1 \leq i \leq  \frac{n+1}{2} $; if $i$ is odd, then the edge $u_i^1u_{i+1}^2$ has weight $i-1+i+1-2+n=n+2i-2$; if $i$ is even, this edge has weight $i_2+i+1-1+n=n+2i-2$. Thus, we have $\frac{n+1}{2}$ edges which weights are $n, n+2, \dots, 2n-1$. Suppose now that $ \frac{n+3}{2} \leq i \leq n$ the edge $u_i^1u_{i+1}^2$ has weight $3n-2i+1$. Thus, we have $\frac{n-1}{2}$ edges whose weights are $n+1, n+3, \dots, 2n-2$. Therefore, the weights of the edges of $C_n \times P_2$ are the integers in $[0, 3n-1]$; which implies that this graph is semi harmonious when $n \equiv 1 (\text{mod } 4)$.
\end{proof}

With this result we are ready to prove that $C_n \times P_m$ is semi harmonious for each $m \geq 1$ and every $n \not \equiv 2(\text{mod } 4)$. In order to simplify the proof of this result we must observe first that Lemma 2.2 is still valid if the vertex $u_i^1$ is connected with $u_{i-1}^2$, where the difference $i-1$ is taken (mod $n$).

\begin{theorem}
If $C_n$ is semi harmonious, then the Cartesian product of $C_n$ and  $P_m$ is a semi harmonious graph for every $m \geq 1$.
\end{theorem}

\begin{proof}
The cases where $m=1, 2$ where considered in Theorem 2.1 or Lemma 2.1, and Lemma 2.2, respectively; so, we are assuming that $m \geq 3$. Let $R_1, R_2, \dots, R_m$ be the copies of $C_n$ in $C_n \times P_m$. Each of these copies is initially labeled following the criteria described in Lemma 2.2. For $i \geq 2$, the labeling on $R_i$ is shifted $n(i-1)$ units. Thus, the labels on $R_j$ and $R_{j+1}$ are $n$ units apart as in Lemma 2.2. We proceed to connect $R_j$ and $R_{j+1}$ in the following form: if $j$ is odd the vertex $u_i^j$ of $R_j$ is connected with the vertex $u_{i+1}^{j+1}$ of $R_{j+1}$, if $j$ is even the vertex $u_i^j$ of $R_j$ is connected with the vertex $u_{i-1}^{j+1}$ of $R_{j+1}$, where the addition $i+1$ and the difference $i-1$ are taken (mod $n$). By Lemma 2.2 we know that the edges connecting $R_j$ and $R_{j+1}$ have weights with the suitable values to complement the weights on the copies of $C_n$, therefore, $C_n \times P_m$ is a semi harmonious graph.
\end{proof}

In Figure 3 we show an example of this semi harmonious labeling for the case $C_9 \times P_3$.\\

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[xscale=0.8,yscale=0.8]

\vertex [fill](1) at (3.5,6.75) [label=above :{18}]{};
\vertex [fill](2) at (1.3,5.9) [label=above left:{18}]{};
\vertex [fill](3) at (0.1,3.8) [label=left:{20}]{};
\vertex [fill](4) at (0.6,1.5) [label=below left:{20}]{};
\vertex [fill](5) at (2.4,0.1) [label=below:{22}]{};
\vertex [fill](6) at (4.6,0.1) [label=below:{22}]{};
\vertex [fill](7) at (6.4,1.5) [label=below right:{21}]{};
\vertex [fill](8) at (6.9,3.8) [label=right:{20}]{};
\vertex [fill](9) at (5.7,5.9) [label=above right:{19}]{};
\draw[thick]	(1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) -- (8) -- (9) -- (1);

\vertex [fill](a1) at (3.5,5.75) [label=above right :{9}]{};
\vertex [fill](a2) at (1.9,5.2) [label=above:{11}]{};
\vertex [fill](a3) at (1.1,3.7) [label=above left:{11}]{};
\vertex [fill](a4) at (1.4,2.1) [label= left:{13}]{};
\vertex [fill](a5) at (2.7,1.1) [label=below left:{13}]{};
\vertex [fill](a6) at (4.3,1.1) [label=below left :{12}]{};
\vertex [fill](a7) at (5.6,2.1) [label=below:{11}]{};
\vertex [fill](a8) at (5.9,3.7) [label=below right:{10}]{};
\vertex [fill](a9) at (5.1,5.2) [label=right:{9}]{};
\draw[thick]	(a1) -- (a2) -- (a3) -- (a4) -- (a5) -- (a6) -- (a7) -- (a8) -- (a9) -- (a1);

\vertex [fill](b1) at (3.5,4.75) [label=below :{0}]{};
\vertex [fill](b2) at (2.6,4.4) [label=below right:{0}]{};
\vertex [fill](b3) at (2.1,3.6) [label=right:{2}]{};
\vertex [fill](b4) at (2.3,2.6) [label=above right:{2}]{};
\vertex [fill](b5) at (3,2) [label=above:{4}]{};
\vertex [fill](b6) at (4,2) [label=above:{4}]{};
\vertex [fill](b7) at (4.7,2.6) [label=above left:{3}]{};
\vertex [fill](b8) at (4.9,3.6) [label=left:{2}]{};
\vertex [fill](b9) at (4.4,4.4) [label=below left:{1}]{};
\draw[thick]	(b1) -- (b2) -- (b3) -- (b4) -- (b5) -- (b6) -- (b7) -- (b8) -- (b9) -- (b1);

\draw[thick]	(1) -- (a1) -- (b1);
\draw[thick]	(2) -- (a2) -- (b2);
\draw[thick]	(3) -- (a3) -- (b3);
\draw[thick]	(4) -- (a4) -- (b4);
\draw[thick]	(5) -- (a5) -- (b5);
\draw[thick]	(6) -- (a6) -- (b6);
\draw[thick]	(7) -- (a7) -- (b7);
\draw[thick]	(8) -- (a8) -- (b8);
\draw[thick]	(9) -- (a9) -- (b9);

\end{tikzpicture}
\caption{Semi harmonious labeling of $C_9 \times P_3$}
\end{center}
\end{figure}

Now we turn our attention to the complete bipartite graph $K_{m,n}$. Let $A$ and $B$ be the stable sets of $K_{m,n}$, Graham and Sloane \cite{925} proved that this graph is harmonious if and only if at least one of the stable sets is a singleton. In the next result we show that $K_{m, n}$ is semi harmonious for all values of $m$ and $n$. But first, we note that if $f$ is semi harmonious labeling of $K_{m,n}$, then $f$ restricted to $A$ or $B$ must be injective, otherwise, we obtain at least two edges with the same weight. This observation can be extended to any complete multipartite graph. Furthermore, for the same reason, i.e., duplication of weights, there are no two labels used on both stable sets or in any two stable sets of a multipartite graph.

\begin{theorem}
The complete bipartite graph $K_{m,n}$ is semi harmonious.
\end{theorem}

\begin{proof}
Assume that $A$ and $B$ are the stable sets of $K_{m,n}$, where $A=\{u_1, u_2, \dots, u_m\}$ and  $B=\{v_1, v_2, \dots, v_n\}$. Consider the labeling $f$ defined on the elements of $A$ as $f(u_i)=i-1$ and on the elements of $B$ as $f(v_j)=m(j-1)+1$. Note that the range of $f$ is $[0, mn-m+1]$, and that $f$ restricted to either $A$ or $B$ is an injective function. For a fixed value of $j$, the weights of the edges $u_iv_j$ form the interval $W_j=[m(j-1)+1, mj]$. Since $\text{max}W_{j-1}=m(j-1) < \text{min}W_j=m(j-1)+1$ and $\cup_{j=1}^nW_j=[1, mn]$, we have that $f$ is indeed a semi harmonious labeling of $K_{m,n}$.
\end{proof}

\section{All Trees are Semi Harmonious}

In this section we prove that all trees are semi harmonious. This result is a consequence of other known results in the area of difference vertex labelings, these labelings are out of the scope of this work and are not discussed here. In order to keep the result self-contained, we describe the labeling of a tree without using these existing results.

\begin{theorem}
All trees are semi harmonious.
\end{theorem}

\begin{proof}
Suppose that $T$ is a tree of size $q$ with stable sets $A$ and $B$ such that $|A|=a$ and $|B|=b$. When $T$ is represented as a rooted tree, with root $v_1^0 \in A$, its vertices are distributed in $h+1$ levels; we denote these levels by $L_0, L_1, \dots, L_h$, being the root the only vertex on level $L_0$. Let $v_1^i, v_2^i, \dots, v_{h_i}^i$ be the vertices of $T$ on $L_i$, which are organized from left to right, that is, $v_j^i$ is placed to the left of $v_{j+1}^i$ for each $i \geq 1$.

Let $f$ be the labeling of $T$ that satisfies the following conditions, where $v_x^{i-1}$ and $v_y^{i-1}$ are the parents of $v_j^i$ and $v_{j+1}^i$, respectively.
\begin{enumerate}[label=(\arabic*)]
	\item $f(v_1^0)=0$,
	\item $f(v_1^1)=a$,
	\item $f(v_j^i) \leq f(v_{j+1}^i)$ for every $1 \leq i \leq h$ and every $1 \leq j \leq h_i$,
	\item if $f(v_x^{i-1})=f(v_y^{i-1})$, then $f(v_{j+1}^i)=f(v_j^i)+1$,
	\item  if $f(v_y^{i-1})=f(v_x^{i-1})+1$, then $f(v_{j+1}^i)=f(v_j^i)$,
	\item  if $f(v_{h_{i-2}}^{i-2})+f(v_{h_{i-1}}^{i-1})=w$, then $f(v_1^{i-1})+f(v_1^i)=w+1$.
\end{enumerate}
We claim that $f$ is a semi harmonious labeling of $T$. In order to prove this claim, we just need to show that the set of induced weights is $\{a, a+1, \dots, a+q-1\}$, i.e., a set of $q$ consecutive integers.

Condition (3) tells us that for every $0 \leq i \leq h$ the sequence $f(v_1^i), f(v_2^i), \dots, f(v_{h_i}^i)$ is non-decreasing.

Note that condition (4) implies two different, but related things. If $v_j^i$ and $v_{j+1}^i$ are siblings, that is, if $v_x^{i-1}=v_y^{i-1}$, then the edges $v_x^{i-1}v_j^i$ and $v_x^{i-1}v_{j+1}^i$ have weights that are consecutive integers because $f(v_{j+1}^i)=f(v_j^i)+1$. The same result is obtained when $v_j^i$ and $v_{j+1}^i$ are not siblings because $f(v_x^{i-1})=f(v_y^{i-1})$ independently of the fact that $v_x^{i-1} \neq v_y^{i-1}$.

Condition (5) guarantees that in the event that $v_j^i$ and $v_{j+1}^i$ are not siblings but $f(v_y^{i-1})=f(v_x^{i-1})+1$, the weights of the edges $v_x^{i-1}v_j^i$ and $v_x^{i-1}v_{j+1}^i$ are consecutive integers because $v_j^i$ and $v_{j+1}^i$ have the same label.

As a conclusion of (3), (4), and (5) we get that the sequence formed by the weights of the edges connecting the vertices of $L_{i-1}$ with the vertices of $L_i$ is an arithmetic sequence of difference 1. Condition (6) says that the largest weight on an edge between vertices of $L_{i-2}$ and $L_{i-1}$ is exactly one unit less than the smallest weight of an edge between vertices of $L_{i-1}$ and $L_i$. Consequently, the weights induced on the edges of $T$ form a set of exactly $q$ consecutive integers. Since $f(v_1^0)=0$ and $f(v_1^1)=a$, the smallest of these weights is $a$.
\end{proof}

This labeling is a modification of the labeling used in \cite{385} to prove that every tree of size $q$ is a spanning tree of an $\alpha$-graph of size $q+\epsilon(T)$, where $\epsilon(T)$ is the excess of $T$ (this parameter was originally introduced in \cite{371}, but its analysis is out of the scope of this work). In \cite{1266} Jungreis and Reid presented a method to transform an $\alpha$-labeling into a sequential labeling, which can be transformed into a harmonious labeling. The semi harmonious labeling of $T$ is obtained combining the results in \cite{385} and \cite{1266}.

In Figure 4 we show the semi harmonious labeling obtained with the procedure described in Theorem 3.1 for a tree of size $q=31$ with stable sets of cardinality $a=b=16$.

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[xscale=0.5,yscale=0.5]

\vertex [fill] (a14) at (14,0) [label=left:{14}]{};
\vertex [fill] (b14) at (16,0) [label=left:{14}]{};
\vertex [fill] (15) at (18,0) [label=left:{15}]{};
\vertex [fill] (8) at (0,4) [label=left:{8}]{};
\vertex [fill] (a9) at (2,4) [label=left:{9}]{};
\vertex [fill] (b9) at (4,4) [label=left:{9}]{};
\vertex [fill] (a10) at (6,4) [label=left:{10}]{};
\vertex [fill] (b10) at (8,4) [label=left:{10}]{};
\vertex [fill] (a11) at (10,4) [label=left:{11}]{};
\vertex [fill] (b11) at (14,4) [label=left:{11}]{};
\vertex [fill] (12) at (18,4) [label=left:{12}]{};
\vertex [fill] (3) at (1,8) [label=left:{3}]{};
\vertex [fill] (a4) at (4,8) [label=left:{4}]{};
\vertex [fill] (b4) at (9,8) [label=left:{4}]{};
\vertex [fill] (c4) at (16,8) [label=left:{4}]{};
\vertex [fill] (0) at (9,12) [label=above:{0}]{};
\vertex [] (27) at (2,2) [label=left:{27}]{};
\vertex [] (a28) at (4,2) [label=left:{28}]{};
\vertex [] (b28) at (6,2) [label=left:{28}]{};
\vertex [] (c28) at (10,2) [label=left:{28}]{};
\vertex [] (29) at (12,2) [label=left:{29}]{};
\vertex [] (30) at (14,2) [label=left:{30}]{};
\vertex [] (a31) at (16,2) [label=left:{31}]{};
\vertex [] (b31) at (18,2) [label=left:{31}]{};
\vertex [] (a20) at (1,6) [label=left:{20}]{};
\vertex [] (b20) at (3,6) [label=left:{20}]{};
\vertex [] (21) at (5,6) [label=left:{21}]{};
\vertex [] (22) at (9,6) [label=left:{22}]{};
\vertex [] (23) at (16,6) [label=left:{23}]{};
\vertex [] (16) at (2.5,10) [label=above:{16}]{};
\vertex [] (17) at (9,10) [label=left:{17}]{};
\vertex [] (18) at (16,10) [label=above:{18}]{};
\draw[thick]	(27) -- (a9) -- (a20) -- (3) -- (16) -- (0) -- (18) -- (c4) -- (23) -- (12) -- (b31) -- (15);
\draw[thick]	(8) -- (a20);
\draw[thick]	(a28) -- (b9) -- (21) -- (a4) -- (16);
\draw[thick]	(b28) -- (a10) -- (21);
\draw[thick]	(c28) -- (a11) -- (22) -- (b4) -- (17) -- (0);
\draw[thick]	(b10) -- (22);
\draw[thick]	(29) -- (b11) -- (23);
\draw[thick]	(a14) -- (30) -- (b11) -- (a31) -- (b14);
\draw[thick]	(b20) -- (a4);

\end{tikzpicture}
\caption{Semi harmonious labeling of a tree of size 31}
\end{center}
\end{figure}


\section{Semi Arithmetic Graphs}

Let $k, d$ be a pair of positive integers, a $(p, q)$-graph $G$ is said to be \emph{semi ($k, d$)-arithmetic} if there exists a labeling $f: V(G) \rightarrow \mathbb{N}$ such that the induced weights are $k, k+d, k+2d, \dots, k+(q-1)d$, i.e., an arithmetic sequence with first element $k$ and difference $d$. As before, the labeling $f$ is called \emph{semi ($k, d$)-arithmetic}. 

Note that all the semi harmonious labelings discussed in the previous section can be seen as semi ($k, d$)-arithmetic labelings where $k=0$ and $d=1$.

In \cite{39}, Acharya and Hegde said that the injection $f:V(G) \rightarrow \{0, 1, \dots, p-1\}$ is \textit{strongly $(k,d)$-indexable} if the set of induced weights is $W=\{k, k+d, \dots, k+d(q-1)\}$. When $d=1$, both the labeling and the graph are said to be \textit{$k$-indexable}, if in addition $k=1$, they are simply called \textit{strongly indexable}.

Let $G$ be a bipartite graph of order $p$ and size $q$, such that $G$ is $k$-indexable where $k \geq 2$. Then, for each $w \in W=\{k, k+1, \dots, k+q-1\}$ there exists $uv \in E(G)$ such that $f(u)+f(v)=w$. If $A$ and $B$ are the stable sets of $G$, we may assume that $u \in A$ and $v \in B$, and that the vertex labeled $0$ belongs to $A$. Consider the labeling $g$ of $G$ defined for each $v \in V(G)$ as
\[
g(v) = \begin{cases}
f(v) & \text{if } v \in A, \\
f(v)+i-k & \text{if } v \in B,
\end{cases}
\]
where $i \geq 1$. Note that $k=\text{min}\{f(v):v \in B\}$; this implies that $f(v)+i-k \geq i$ for every $v \in B$. Let $uv \in E(G)$ such that $f(u)+f(w)=w$, since $G$ is bipartite $u$ and $v$ are in different stable sets, therefore
\[g(u)+g(v)=f(u)+f(v)+i-k=w+i-k.\]
This implies that the set of weights induced by $g$ is $\{i, i+1, \dots, i+q-1\}$. Consequently, $g$ is a semi $(i, 1)$-arithmetic labeling of $G$. In this way we have proven the next theorem.

\begin{theorem}
If $G$ is a bipartite $k$-indexable graph with $k \geq 2$, then $G$ admits a semi $(i, 1)$-arithmetic labeling for each $i \geq 1$.
\end{theorem}

Germina \cite{866} proved that for each odd value of $n$, the ladder $L_n = P_n \times P_2$ is $k$-indexable when $k=\frac{n+1}{2}$. Therefore, we can apply the result of Theorem 4.1 to these graphs. In Figure 5 we use the labeling of $L_7$ given in \cite{866} to show the semi $(i, 1)$-arithmetic labeling described before, for each $i \in \{1, 2, 3, 4, 5\}$, being the case $i=4$ the one given in \cite{866}.

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[xscale=0.6,yscale=0.6]



\vertex [fill] (1) at (0,6) [label=left:{0}]{};
\vertex [] (2) at (0,5) [label=left:{5}]{};
\vertex [fill] (3) at (0,4) [label=left:{1}]{};
\vertex [] (4) at (0,3) [label=left:{6}]{};
\vertex [fill] (5) at (0,2) [label=left:{2}]{};
\vertex [] (6) at (0,1) [label=left:{7}]{};
\vertex [fill] (7) at (0,0) [label=left:{3}]{};
\vertex [] (8) at (1.5,0) [label= right:{14}]{};
\vertex [fill] (9) at (1.5,1) [label=right:{9}]{};
\vertex [] (10) at (1.5,2) [label=right:{13}]{};
\vertex [fill] (11) at (1.5,3) [label=right:{8}]{};
\vertex [] (12) at (1.5,4) [label=right:{12}]{};
\vertex [fill] (13) at (1.5,5) [label=right:{7}]{};
\vertex [] (14) at (1.5,6) [label=right:{11}]{};
\draw[thick]	(1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) --(8) -- (9) -- (10) -- (11) --(12) -- (13) -- (14) -- (1);
\draw[thick]	(2) -- (13);
\draw[thick]	(3) -- (12);
\draw[thick]	(4) -- (11);
\draw[thick]	(5) -- (10);
\draw[thick]	(6) -- (9);

\vertex [fill] (1) at (4.5,6) [label=left:{0}]{};
\vertex [] (2) at (4.5,5) [label=left:{4}]{};
\vertex [fill] (3) at (4.5,4) [label=left:{1}]{};
\vertex [] (4) at (4.5,3) [label=left:{5}]{};
\vertex [fill] (5) at (4.5,2) [label=left:{2}]{};
\vertex [] (6) at (4.5,1) [label=left:{6}]{};
\vertex [fill] (7) at (4.5,0) [label=left:{3}]{};
\vertex [] (8) at (6,0) [label= right:{13}]{};
\vertex [fill] (9) at (6,1) [label=right:{9}]{};
\vertex [] (10) at (6,2) [label=right:{12}]{};
\vertex [fill] (11) at (6,3) [label=right:{8}]{};
\vertex [] (12) at (6,4) [label=right:{11}]{};
\vertex [fill] (13) at (6,5) [label=right:{7}]{};
\vertex [] (14) at (6,6) [label=right:{10}]{};
\draw[thick]	(1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) --(8) -- (9) -- (10) -- (11) --(12) -- (13) -- (14) -- (1);
\draw[thick]	(2) -- (13);
\draw[thick]	(3) -- (12);
\draw[thick]	(4) -- (11);
\draw[thick]	(5) -- (10);
\draw[thick]	(6) -- (9);

\vertex [fill] (1) at (9,6) [label=left:{0}]{};
\vertex [] (2) at (9,5) [label=left:{3}]{};
\vertex [fill] (3) at (9,4) [label=left:{1}]{};
\vertex [] (4) at (9,3) [label=left:{4}]{};
\vertex [fill] (5) at (9,2) [label=left:{2}]{};
\vertex [] (6) at (9,1) [label=left:{5}]{};
\vertex [fill] (7) at (9,0) [label=left:{3}]{};
\vertex [] (8) at (10.5,0) [label= right:{12}]{};
\vertex [fill] (9) at (10.5,1) [label=right:{9}]{};
\vertex [] (10) at (10.5,2) [label=right:{11}]{};
\vertex [fill] (11) at (10.5,3) [label=right:{8}]{};
\vertex [] (12) at (10.5,4) [label=right:{10}]{};
\vertex [fill] (13) at (10.5,5) [label=right:{7}]{};
\vertex [] (14) at (10.5,6) [label=right:{9}]{};
\draw[thick]	(1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) --(8) -- (9) -- (10) -- (11) --(12) -- (13) -- (14) -- (1);
\draw[thick]	(2) -- (13);
\draw[thick]	(3) -- (12);
\draw[thick]	(4) -- (11);
\draw[thick]	(5) -- (10);
\draw[thick]	(6) -- (9);

\vertex [fill] (1) at (13.5,6) [label=left:{0}]{};
\vertex [] (2) at (13.5,5) [label=left:{2}]{};
\vertex [fill] (3) at (13.5,4) [label=left:{1}]{};
\vertex [] (4) at (13.5,3) [label=left:{3}]{};
\vertex [fill] (5) at (13.5,2) [label=left:{2}]{};
\vertex [] (6) at (13.5,1) [label=left:{4}]{};
\vertex [fill] (7) at (13.5,0) [label=left:{3}]{};
\vertex [] (8) at (15,0) [label= right:{11}]{};
\vertex [fill] (9) at (15,1) [label=right:{9}]{};
\vertex [] (10) at (15,2) [label=right:{10}]{};
\vertex [fill] (11) at (15,3) [label=right:{8}]{};
\vertex [] (12) at (15,4) [label=right:{9}]{};
\vertex [fill] (13) at (15,5) [label=right:{7}]{};
\vertex [] (14) at (15,6) [label=right:{8}]{};
\draw[thick]	(1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) --(8) -- (9) -- (10) -- (11) --(12) -- (13) -- (14) -- (1);
\draw[thick]	(2) -- (13);
\draw[thick]	(3) -- (12);
\draw[thick]	(4) -- (11);
\draw[thick]	(5) -- (10);
\draw[thick]	(6) -- (9);

\vertex [fill] (1) at (18,6) [label=left:{0}]{};
\vertex [] (2) at (18,5) [label=left:{1}]{};
\vertex [fill] (3) at (18,4) [label=left:{1}]{};
\vertex [] (4) at (18,3) [label=left:{2}]{};
\vertex [fill] (5) at (18,2) [label=left:{2}]{};
\vertex [] (6) at (18,1) [label=left:{3}]{};
\vertex [fill] (7) at (18,0) [label=left:{3}]{};
\vertex [] (8) at (19.5,0) [label= right:{10}]{};
\vertex [fill] (9) at (19.5,1) [label=right:{9}]{};
\vertex [] (10) at (19.5,2) [label=right:{9}]{};
\vertex [fill] (11) at (19.5,3) [label=right:{8}]{};
\vertex [] (12) at (19.5,4) [label=right:{8}]{};
\vertex [fill] (13) at (19.5,5) [label=right:{7}]{};
\vertex [] (14) at (19.5,6) [label=right:{7}]{};
\draw[thick]	(1) -- (2) -- (3) -- (4) -- (5) -- (6) -- (7) --(8) -- (9) -- (10) -- (11) --(12) -- (13) -- (14) -- (1);
\draw[thick]	(2) -- (13);
\draw[thick]	(3) -- (12);
\draw[thick]	(4) -- (11);
\draw[thick]	(5) -- (10);
\draw[thick]	(6) -- (9);

\end{tikzpicture}
\caption{Semi $(i, 1)$-arithmetic labelings of $L_7=P_7 \times P_2$ for each $i \in \{1,2,3,4,5\}$}
\end{center}
\end{figure}

Next we present another general property of the semi $(k, d)$-arithmetic labelings.

\begin{proposition}
If $G$ is a semi $(k, d)$-arithmetic graph, then $G$ is a semi $(rk, rd)$-arithmetic graph for each $r \geq 2$.
\end{proposition}

\begin{proof}
Let $G$ be a graph of size $q$ and $f$ be a semi $(k, d)$-arithmetic labeling of $G$. Thus, the set of weights induced by $f$ is $W=\{k, k+d, \dots, k+d(q-1)\}$. Then, for every $w \in W$ there exists $uv \in E(G)$ such that $f(u)+f(v)=w$. Let $g$ be the labeling of $G$ defined, for every $v \in V(G)$, by $g(v)=rf(v)$ for some $r \geq 2$. The weight induced by $g$ on the edge $uv$ is:
\[g(u)+g(v)=r(f(u)+f(v))=rw.\]
Since $w=k+di$, for some $i \in \{0, 1, \dots, q-1\}$, we have that the new weight of $uv$ is $rk+rdi$. In other terms, the set of weights induced by $g$ is $W'=\{rk, rk+rd, \dots, rk+rd(q-1)\}$, i.e., these weights form an arithmetic sequence of difference $rd$ and first element $rk$. Therefore, $g$ is a semi $(rk, rd)$-arithmetic labeling of $G$.
\end{proof}


Recall that the union of $n$ copies of a graph $G$ is denoted by $nG$. In the following results we work with semi ($k, d$)-arithmetic labelings of graphs of the form $nG$.

\begin{theorem}
Let $G$ be a ($p, q$)-graph of even size and $k, d$ be a pair of positive integers. If $G$ is semi ($k, d$)-arithmetic, then for every positive integer $n$ the graph $nG$ is semi ($k, d$)-arithmetic.
\end{theorem}

\begin{proof}
Let $G$ be a semi ($k, d$)-arithmetic graph of order $p$ and even size $q$ with $V(G)=\{u_1, u_2, \dots, u_p\}$. For each $i \in [1, n]$, let $G_i$ be a copy of $G$, where $V(G_i)=\{u_1^i, u_2^i, \dots, u_p^i\}$ and $u_j^i$ be the replica of $u_j$. Suppose that $f$ is a semi ($k, d$)-arithmetic labeling of $G$. This labeling can be extended to a semi ($k, d$)-arithmetic labeling $g$ of $nG$. For each vertex $u_j^i$ of $nG$, where $j \in [1, p]$ and $i \in [1, n]$, $g(u_j^i)=f(u_j)+\frac{qd(i-1)}{2}$.

Since $G$ is a semi ($k, d$)-arithmetic graph, the set of weights induced on the edges of $G_i$ is $W_i=[k+qd(i-1), k+qd(i-1)+(q-1)d]_d=[k+(i-1)qd, k+iqd-d]_d$. Thus,
\[
\bigcup_{i=1}^nW_i=[k, k+(nq-1)d]_d.
\]
Hence, $g$ is a semi ($k, d$)-arithmetic labeling of $nG$ as we claimed.
\end{proof}

\begin{theorem}
Let $G$ be a ($p, q$)-graph of odd size and $k, d$ be a pair of positive integers. If $G$ is semi ($k, d$)- and ($k+d, d$)-arithmetic, then for every positive integer $n$ the graph $nG$ is also semi ($k, d$)- and ($k+d, d$)-arithmetic.
\end{theorem}

\begin{proof}
Let $G$ be a semi ($k, d$)-arithmetic and semi ($k+d, d$)-arithmetic graph of order $p$ and odd size $q$ with $V(G)=\{u_1, u_2, \dots, u_p\}$. For each $i \in [1, n]$, let $G_i$ be a copy of $G$, where $V(G_i)=\{u_1^i, u_2^i, \dots, u_p^i\}$ and $u_j^i$ be the replica of $u_j$. Suppose that $f$ and $g$ are a semi ($k, d$)-arithmetic labeling and a semi ($k+d, d$)-arithmetic labeling of $G$, respectively.

We show first that $nG$ is a a semi ($k, d$)-arithmetic graph. Consider the following labeling of the vertices of $nG$:
\[
h(u_i) = \begin{cases}
f(u_j)+\frac{dq(i-1)}{2} & \text{if } i \text{ is odd}, \\
g(u_j)+\frac{d(q(i-1)-1)}{2} & \text{if } i \text{ is even}.
\end{cases}
\]
Note that all the labels assigned by $h$ are nonnegative integers. Let $W_i$ be the set formed by the weights induced by $h$ on the edges of $G_i$. Independently of the parity of $i$, we get that $W_i=[k+dq(i-1), k+d(qi-1)]_d$. Since,
$$\text{min}W_i-\text{max}W_{i-1}=(k+dq(i-1))-(k+d(q(i-1)-1)=d,$$
we conclude that the weights induced by $h$ on the edges of $nG$ form an arithmetic sequence of difference $d$ which first and last elements are $k$ and $k+d(qn-1)$, respectively. Based on the fact that this sequence has $qn$ terms, we have that there are no repeated weights. Consequently, $h$ is a semi ($k, d$)-arithmetic labeling of $nG$.

Now we prove that $nG$ is semi ($k+d, d$)-arithmetic. Let $h'$ be the labeling of $nG$ defined on the vertices of $G_i$ as:
\[
h'(u_i) = \begin{cases}
g(u_j)+\frac{dq(i-1)}{2} & \text{if } i \text{ is odd}, \\
f(u_j)+\frac{d(q(i-1)+1)}{2} & \text{if } i \text{ is even}.
\end{cases}
\]
As in the previous case, regardless the parity if $i$, the set formed by the weights on the edges of $G_i$ is $W_i=k+d(q(i-1)+1, k+dqi]_d$. Again,
$$\text{min}W_i-\text{max}W_{i-1}=(k+dq(i+1))-(k+d(q(i-1)-1)=d,$$
which implies that the weights on the edges of $nG$ form an arithmetics sequence of difference $d$ which first and last elements are $k+d$ and $k+dqn$, respectively. Thus, $h'$ is a semi ($k+d, d$)-arithmetic labeling of $nG$.
\end{proof}

Now, we turn our attention to the complete bipartite graphs. In \cite{925}, Graham and Sloane proved that $K_{m, n}$ is harmonious if and only if it is acyclic. Bu and Shi \cite{513} proved that $K_{m, n}$ is ($k, d$)-arithmetic if $k \neq id$ for each positive $i \leq n-1$. Lu et al. \cite{1673} proved that $K_{1, m} \cup K_{p, qn}$ is ($k, d$)-arithmetic if $d \neq 1$ and $k > d(q-1)+1$. In the following lemma we show that $K_{m, n}$ is semi ($k, d$)-arithmetic for any pair $k, d$ of positive integers.


\begin{lemma}
The complete bipartite graph $K_{m, n}$ is semi ($k, d$)-arithmetic for every pair $k, d$ of positive integers.
\end{lemma}

\begin{proof}
Let $A=\{u_1, u_2, \dots, u_m\}$ and $B=\{v_1, v_2, \dots, v_n\}$ be the stable sets of $K_{m, n}$. Consider the following labeling of the vertices of $K_{m, n}$:
\begin{itemize}
	\item $f(u_i)=nd(i-1)$ for each $1 \leq i \leq m$,
	\item $f(v_v)=k+d(j-1)$ for each $1 \leq j \leq n$.
\end{itemize}
Since all the parameters and variables involved in the definition of $f$ are positive integers, we conclude that the range of $f$ is a subset of $\mathbb{N}$. Note that
\[
f(u_i)+f(v_j)=nd(i-1)+k+d(j-1)=k+d(n(i-1)+j-1).
\]
Thus, for a fixed value of $i$, the set of weights induced on the edges $u_iv_j$ is
\[
W_i=\{k+dn(i-1), k+dn(i-1)+d, \dots, k+dn(i-1)+d(n-1)\}.
\]
Since $i \in \{1, 2, \dots, m\}$, the union of these sets is $\cup_{i=1}^mW_i=\{k, k+d, \dots, k+d(mn-1)\}.$

Therefore, the labeling $f$ is semi ($k, d$)-arithmetic.
\end{proof}

In the following result we prove that this labeling of $K_{m, n}$ can be extended to an arbitrary union of complete bipartite graphs.

\begin{theorem}
If $G$ is a graph which components are complete bipartite graphs, then $G$ is semi ($k, d$)-arithmetic.
\end{theorem}

\begin{proof}
Let $G=\cup_{t=1}^rK_{m_t, n_t}$ and $A_t=\{u_1^t, u_2^t, \dots, u_m^t\}$ and $B_t=\{v_1^t, v_2^t, \dots, v_n^t\}$ be the stable sets of $K_{m_t, n_t}$. Basically, the labeling of each component of $G$ follows the pattern of the labeling $f$ described in the previous lemma. In particular, the labeling of $K_{m_1, n_1}$ is $f$ itself. For $t \geq 2$, the labeling of $K_{m_t, n_t}$ depends on the labeling of $K_{m_{t-1}, n_{t-1}}$; if $xd$ is the label on $u_{m_{t-1}}^{t-1}$, then the label on $u_1^t$ is $(x-1)d$, if $k+yd$ is the label on $v_{n_{t-1}}^{t-1}$, then the label on $v_1^t$ is $k+(y+2)d$. Therefore, the largest weight on an edge of $K_{m_{t-1}, n_{t-1}}$ is $k+d(x+y)$ and the smallest weight on an edge of $K_{m_t, n_t}$ is $(x-1)d+k+(y+2)d=k+d(x+y+1)$.

Consequently, the weights on the edges of $K_{m_t, n_t}$ form an arithmetic sequence of difference $d$ which first element is $k+d(x+y+1)$. As a result of this, we have that the weights on the edges of $G$ form an arithmetic sequence of difference $d$ which first element is $k$. Hence, $G$ is a semi ($k, d$)-arithmetic graph.
\end{proof}

In Figure 6 we show an example of this labeling for a graph $G$ which components are $K_{3, 3}$, $K_{3, 4}$, and $K_{4, 3}$.

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[xscale=0.9,yscale=0.9]

\vertex [fill] (1) at (1,1) [label=left:{$6d$}]{};
\vertex [fill] (2) at (1,2) [label=left:{$3d$}]{};
\vertex [fill] (3) at (1,3) [label=left:{$0$}]{};
\vertex [] (4) at (3,1) [label=right:{$k+2d$}]{};
\vertex [] (5) at (3,2) [label=right:{$k+d$}]{};
\vertex [] (6) at (3,3) [label=right:{$k$}]{};
\draw[thick]	(4) -- (1) -- (5);
\draw[thick]	(4) -- (2) -- (5);
\draw[thick]	(4) -- (3) -- (5);
\draw[thick]	(1) -- (6) -- (2);
\draw[thick]	(6) -- (3);

\vertex [fill] (1) at (6,1) [label=left:{$13d$}]{};
\vertex [fill] (2) at (6,2) [label=left:{$9d$}]{};
\vertex [fill] (3) at (6,3) [label=left:{$5d$}]{};
\vertex [] (4) at (8,0.5) [label=right:{$k+7d$}]{};
\vertex [] (5) at (8,1.5) [label=right:{$k+6d$}]{};
\vertex [] (6) at (8,2.5) [label=right:{$k+5d$}]{};
\vertex [] (7) at (8,3.5) [label=right:{$k+4d$}]{};
\draw[thick]	(4) -- (1) -- (5);
\draw[thick]	(6) -- (1) -- (6);
\draw[thick]	(4) -- (2) -- (5);
\draw[thick]	(6) -- (2) -- (6);
\draw[thick]	(4) -- (3) -- (5);
\draw[thick]	(6) -- (3) -- (6);
\draw[thick]	(1) -- (7) -- (2);
\draw[thick]	(3) -- (7);

\vertex [fill] (1) at (11,0.5) [label=left:{$21d$}]{};
\vertex [fill] (2) at (11,1.5) [label=left:{$18d$}]{};
\vertex [fill] (3) at (11,2.5) [label=left:{$15d$}]{};
\vertex [fill] (4) at (11,3.5) [label=left:{$12d$}]{};
\vertex [] (5) at (13,1) [label=right:{$k+11d$}]{};
\vertex [] (6) at (13,2) [label=right:{$k+10d$}]{};
\vertex [] (7) at (13,3) [label=right:{$k+9d$}]{};
\draw[thick]	(1) -- (5) -- (2);
\draw[thick]	(3) -- (5) -- (4);
\draw[thick]	(1) -- (6) -- (2);
\draw[thick]	(3) -- (6) -- (4);
\draw[thick]	(1) -- (7) -- (2);
\draw[thick]	(3) -- (7) -- (4);

\end{tikzpicture}
\caption{Semi ($k, d$)-arithmetic labeling of $K_{3,3} \cup K_{3,4} \cup K_{4,3}$}
\end{center}
\end{figure}

\begin{theorem}
For $i=1,2$, let $G_i$ be a semi $(k_i, d)$-arithmetic graph of size $q_i$, where $dq_1 \geq k_2-k_1 > 0$. The graph $G_1 \cup G_2$ is semi $(k_1, d)$-arithmetic if one of the following conditions holds:
\begin{enumerate} [label=(\arabic*)]
	\item $k_1$ and $k_2$ have the same parity and $dq_1$ is even, or
	\item $k_1$ and $k_2$ have different parity and $dq_1$ is odd.
\end{enumerate}
\end{theorem}

\begin{proof}
Suppose that $f_i$ is a semi $(k_i, d)$-arithmetic labeling of $G_i$. Consider the labeling $h:V(G_1 \cup G_2) \rightarrow \mathbb{N}$ defined as
\[
h(v) = \begin{cases}
f_1(v) & \text{if } v \in V(G_1), \\
f_2(v)+\frac{k_1+dq_1-k_2}{2} & \text{if } v \in V(G_2).
\end{cases}
\]
We claim that $h$ is a semi $(k_1, d)$-arithmetic labeling of $G_1 \cup G_2$. In order to prove our claim, we note first that the fraction $\frac{k_1+dq_1-k_2}{2}$ is a nonnegative integer because of conditions (1) or (2). Observe now that the weights induced by $h$ of the edges of $G_1$ are $k_1, k_1+d, \dots, k_1+d(q_1-1)$. Since $f_2$ is a semi $(k_2, d)$-arithmetic labeling of $G_2$, it induces the weights $k_2, k_2+d, \dots, k_2+d(q_2-1)$. This implies that the weights induced by $h$ on the edges of $G_2$ are the same numbers but shifted $k_1+dq_1-k_2$ units, that is, $k_1+dq_1, k_1+d(q_1+1), \dots, k_1+d(q_1+q_2-1)$. Therefore, the weights induced by $h$ on the edges of $G_1 \cup G_2$ form an arithmetic sequence of difference $d$ and first element $k_1$. Consequently, $h$ is a semi $(k_1, d)$-arithmetic labeling as we claimed.
\end{proof}



%\section*{Acknowledgement} 
%Write support, acknowledgment, dedicatory, and grants here.

%\section*{References} 
\begin{thebibliography}{99}
\bibitem{39} B. D. Acharya and S. M. Hegde, Arithmetic graphs, \textit{J. Graph Theory}, \textbf{14} (1990) 275--299.
\bibitem{371} C. Barrientos and E. Krop, Improved bounds for relaxed graceful trees, \textit{Graphs Combin.}, \textbf{33} (2017) 287--305.
\bibitem{385} C. Barrientos and S. Minion, New advances in Kotzig's conjecture, \textit{Fundamental J. Math. Appl.}, \textbf{2(2)} (2019) 186--194.
\bibitem{513} C. Bu and J. Shi, A class of ($k,d$)-arithmetic graphs, \textit{J. Harbin Eng. Univ.}, \textbf{16} (1995) 79--81.
\bibitem{558} G. J. Chang, D. F. Hsu, and D. G. Rogers, Additive variations on a graceful theme: some results on harmonious and other related graphs, \textit{Congr. Numer.}, \textbf{32} (1981) 181--197.
\bibitem{CL}G. Chartrand and L. Lesniak-Foster, \textit{Graphs \& Digraphs}, 3rd Edition, CRC Press, 1996.
\bibitem{Fau} R.J. Faudree, M.S. Jacobson, J. Lehel and R.H. Schelp, Irregular networks, regular graphs and integer matrices with distinct row and column sums, \textit{Discrete Math.}, \textbf{76} (1989) 223--240.

\bibitem{Ga} J. A. Gallian, A dynamic survey of graph labeling, 23rd edition, \textit{Elect. J. Combin.}, (2020). 
\bibitem{866} K. A. Germina, More on classes of strongly indexable graphs, \textit{European J. Pure and Applied Math.}, \textbf{3-2} (2010) 269--281.

\bibitem{925} R. L. Graham and N. J. A. Sloane, On additive bases and harmonious graphs, \textit{SIAM J. Alg. Discrete Methods}, \textbf{1} (1980) 382--404.
\bibitem{1266} D. Jungreis and M. Reid, Labeling grids, \textit{Ars Combin.}, \textbf{34} (1992) 167--182.
\bibitem{1532} S. M. Lee, E. Schmeichel, and S.C. Shee, On felicitous graphs, \textit{Discrete Math.}, \textbf{93} (1991) 201--209.
\bibitem{1656} A. Lourdusamy and M. Seenivasan, Vertex equitable labeling of graphs, \textit{J. Discrete Math. Sci, Crypt.}, \textbf{11} (2008) 727--735.
\bibitem{1673} X. Lu, W. Pan, and X. Li, $k$-gracefulness and arithmetic of graph $St(m) \cup K_{p,q}$,  \textit{J. Jilin Univ.}, \textbf{42} (2004) 333--336.
\bibitem{2873} M. Z. Youssef, Two general results on harmonious labelings, \textit{Ars Combin.}, \textbf{68} (2003) 225--230.
\end{thebibliography}

\end{document}

%%
%% End of file `ecrc-template.tex'. 