Linear Forest mP₃ Plus a Longer Path P_n Becoming Antimagic

Abstract

An edge labeling of a graph G is a bijection f from $E(G)$ to a set of $|E(G)|$ integers. For a vertex u in G, the induced vertex sum of u, denoted by $f^{+}(u)$, is defined as $f^{+}(u)={\sum }_{uv\in E(G)}f(uv)$. Graph G is said to be antimagic if it has an edge labeling g such that $g(E(G))=\{1,2,\cdots ,|E(G)|\}$ and $g^{+}(u)\ne g^{+}(v)$ for any pair $u,v\in V(G)$ with $u\ne v$. A linear forest is a union of disjoint paths of orders greater than one. Let $m{P}_k$ denote a linear forest consisting of m disjoint copies of path $P_k$. It is known that $m{P}_3$ is antimagic if and only if $m=1$. In this study, we add a disjoint path $P_n$ ($n\ge 4$) to $m{P}_3$ and develop a necessary condition and a sufficient condition whereby the new linear forest $m{P}_3\bigcup P_n$ may be antimagic.

1. Introduction and Preliminaries

An edge labeling of a graph G is a bijection f from $E(G)$ to a set of $|E(G)|$ integers. For a vertex u in G, the induced vertex sum of u, denoted by $f^{+}(u)$, is defined as $f^{+}(u)={\sum }_{uv\in E(G)}f(uv)$. Graph G is said to be antimagic if it has an edge labeling g such that $g(E(G))=\{1,2,\cdots ,|E(G)|\}$ and $g^{+}(u)\ne g^{+}(v)$ for any pair $u,v\in V(G)$ with $u\ne v$. Such an edge labeling g is called an antimagic labeling of G. Hartsfield and Ringel introduced antimagic graphs in 1990 [1]. They showed that paths $P_n$ $(n\ge 3)$, cycles $C_n$ $(n\ge 3)$, wheels, and complete graphs $K_n$ $(n\ge 3)$ are antimagic. Moreover, they have the following conjecture. Conjecture A: All connected graphs, except for $K_2$, are antimagic. Although many types of connected graphs have been verified to be antimagic in recent decades [1,2,3,4,5,6,7,8,9,10,11,12,13,14], Conjecture A remains open. As an extension, we study the antimagicness of disconnected graphs. We now list several known results as follows. For $n\in N$, a star $S_n$ is a complete bipartite graph $K_{1,n}$. Let $A\bigcup B$ denote the union of disjoint graphs A and B, and $mG$ the union of m disjoint copies of graph G. Wang et al. [15] proved that $2P_{n+1}$, $m{S}_n$ $(m\ge 1)$, $S_n\bigcup P_n$, and $S_n\bigcup P_{n+1}$ are antimagic for $n\ge 3$, and $C_n\bigcup S_k$ is antimagic for $n\ge 3$ and $k\ge 2\sqrt{n}+2$. A star forest is a union of disjoint stars. It is obvious that any star forest containing $S_1$ as its component is not antimagic. Ref. [15] shows that a star forest $m{S}_2$ is antimagic if and only if $m=1$. An $S_k$-free star forest is a star forest without any star $S_k$ as its component. Shang et al. [16] proved that an $S_1$-free star forest containing at most one $S_2$ as its component is antimagic. In addition, they added a star $S_n$ $(n\ge 3)$ to $m{S}_2$ and proved that the star forest $m{S}_2\bigcup S_n$ is antimagic if and only if $m\le min\{{\displaystyle 2n+1,\frac{2n-5+\sqrt{8n^2-24n+17}}{2}}\}$. Chen et al. [17] used a different labeling method to show that $m{S}_2\bigcup S_n$ $(n\ge 3)$ is antimagic if and only if $n\ge max\{{\displaystyle \frac{m-1}{2},\frac{1-2m+\sqrt{8m^2+16m+9}}{2}}\}$. These two results are equivalent as $m\le min\{{\displaystyle 2n+1,\frac{2n-5+\sqrt{8n^2-24n+17}}{2}}\}$ if and only if $n\ge max\{{\displaystyle \frac{m-1}{2},\frac{1-2m+\sqrt{8m^2+16m+9}}{2}}\}$ for $m,n\in N$. Chen et al. also proposed a necessary condition and a sufficient condition for a star forest $m{S}_2\bigcup S_{n_1}\bigcup S_{n_2}\bigcup \cdots \bigcup S_{n_k}$ $(n_1,n_2,\cdots ,n_k\ge 3)$ to be antimagic. In addition, they showed that a star forest with an extra disjoint path is antimagic. A linear forest is a union of disjoint paths of orders greater than one. A $P_k$-free linear forest is a linear forest without any path $P_k$ as its component. Shang [18] showed that $P_2,P_3,P_4$-free linear forests are antimagic. Furthermore, Shang [19] achieved a progressive result showing that $P_2,P_3$-free linear forests are antimagic. As $m{P}_3$ is isomorphic to $m{S}_2$, it is seen that $m{P}_3$ is antimagic if and only if $m=1$. A graph G is said to be k-shifted antimagic ($k\in Z$) if it has an edge labeling f such that $f(E(G))=\{k+1,k+2,\cdots ,k+|E(G)|\}$ and $f^{+}(u)\ne f^{+}(v)$ for any pair $u,v\in V(G)$ with $u\ne v$. From the definition we see that an antimagic graph is 0-shifted antimagic. Graph G is called absolutely antimagic if it is k-shifted antimagic for any $k\in Z$. Recently, Dhananjaya and Li [20] extended the results in [16,18] showing that $S_1,S_2$-free star forests and $P_2,P_3,P_4$-free linear forests are absolutely antimagic. Moreover, they proved that the odd tree forests are absolutely antimagic.

Since any graph containing $P_2$ as component is not antimagic, and [19] shows that $P_2,P_3$-free linear forests are antimagic, the following problem is naturally raising: How many disjoint paths $P_3$ can be added to a $P_2,P_3$-free linear forest such that the extended new linear forest is still antimagic? This problem might not be very easy to answer. Hence, this study begins with the following smaller topic: For a non-antimagic linear forest $m{P}_3$ ($m\ge 2$), we add a longer path $P_n$ ($n\ge 4$) to it and investigate the antimagicness of $m{P}_3\bigcup P_n$. In the following section, we will develop a necessary condition and a sufficient condition whereby the linear forest $m{P}_3\bigcup P_n$ may be antimagic.

2. Conditions for $m{P}_3\bigcup P_n$ ($n\ge 4$) to Be Antimagic

It is known that the linear forest $m{P}_3$ is antimagic if and only if $m=1$ [15]. However, with an extra path $P_n$ $(n\ge 4)$ added to $m{P}_3$ ($m\ge 2$), the linear forest $m{P}_3\bigcup P_n$ may be antimagic. In [18], it was conjectured that if $m{P}_3\bigcup P_4$ is antimagic then $m\le 2$. This conjecture is correct, and in the following we prove a necessary condition for the linear forest $m{P}_3\bigcup P_n$ $(n\ge 4)$ to be antimagic.

Theorem 1.

For $n\ge 4$, if the linear forest $m{P}_3\bigcup P_n$ is antimagic, then ${\displaystyle m\le \frac{2n-7+\sqrt{8n^2-40n+49}}{2}}$.

Proof. 

We first let $f:E(m{P}_3\bigcup P_n)\to \{1,2,\cdots ,2m+n-1\}$ be an antimagic labeling of $m{P}_3\bigcup P_n$. It is observed that in $m{P}_3\bigcup P_n$ there are $n-3$ edges whose both ends are vertices of degree two. Now suppose that these $n-3$ edges receive labels ${\ell }_1,{\ell }_2,\cdots ,{\ell }_{n-3}$ under labeling f, where ${\ell }_1<{\ell }_2<\cdots <{\ell }_{n-3}$. Next, we designate the vertices of degree two in $m{P}_3\bigcup P_n$ as $z_1,z_2,\cdots ,z_{m+n-2}$. We now evaluate the summation of the vertex sums $f^{+}(z_1),f^{+}(z_2),\cdots ,f^{+}(z_{m+n-2})$. It is evident that

$${\displaystyle {\displaystyle \sum _{i=1}^{m+n-2}}{f}^{+}(z_i)={\displaystyle \sum _{i=1}^{2m+n-1}}i+{\displaystyle \sum _{i=1}^{n-3}}{\ell }_i}.$$

(1)

Next, let $A=\{f^{+}(u)|u\in V(m{P}_3\bigcup P_n)\mathrm{and}u\mathrm{has}\mathrm{degree}\mathrm{one}\}$. It is evident that $A=\{1,2,\cdots ,2m+n-1\}-\{{\ell }_1,{\ell }_2,\cdots ,{\ell }_{n-3}\}$. Now, let $b_i$ be the i-th least number in the set $\{f^{+}(z_1),f^{+}(z_2),\cdots ,f^{+}(z_{m+n-2})\}$, for $i=1,2,\cdots ,m+n-2$. Since all vertices have distinct vertex sums under the antimagic labeling f, we have $b_i\notin A$ for $i=1,2,\cdots ,m+n-2$. That is, $b_i\in \{{\ell }_1,{\ell }_2,\cdots ,{\ell }_{n-3}\}\bigcup \{k\in N|k\ge 2m+n\}$. Then,

$b_i\ge {\ell }_i$, for $i=1,2,\cdots ,n-3$, and

$b_i\ge 2m+2+i$, for $i=n-2,n-1,\cdots ,m+n-2$.

Hence,

$${\displaystyle {\displaystyle \sum _{i=1}^{m+n-2}}{b}_i\ge {\displaystyle \sum _{i=1}^{n-3}}{\ell }_i+{\displaystyle \sum _{i=n-2}^{m+n-2}}(2m+2+i)}.$$

(2)

As ${\displaystyle {\displaystyle \sum _{i=1}^{m+n-2}}{f}^{+}(z_i)={\displaystyle \sum _{i=1}^{m+n-2}}{b}_i}$, according to (1) and (2), we have

$${\displaystyle {\displaystyle \sum _{i=1}^{2m+n-1}}i\ge {\displaystyle \sum _{i=n-2}^{m+n-2}}(2m+2+i)}$$

Then, we have

$$\begin{array}{ccc}& & m^2-(2n-7)m+3n-n^2\le 0\hfill \\ & \Rightarrow & {(m-\frac{2n-7}{2})}^2-\frac{8n^2-40n+49}{4}\le 0,\mathrm{where}8n^2-40n+49>0,\mathrm{for}n\ge 4\hfill \\ & \Rightarrow & (m-\frac{2n-7-\sqrt{8n^2-40n+49}}{2})(m-\frac{2n-7+\sqrt{8n^2-40n+49}}{2})\le 0\hfill \\ & \Rightarrow & m\le \frac{2n-7+\sqrt{8n^2-40n+49}}{2}.\hfill \end{array}$$

□

To develop a sufficient condition for $m{P}_3\bigcup P_n$ to be antimagic, we now designate the vertices in $m{P}_3\bigcup P_n$ as follows: The i-th copy of the path $P_3$ in $m{P}_3\bigcup P_n$ is denoted by $x_i{z}_i{y}_i$; the path $P_n$ is denoted by

$$u_1{u}_2{u}_3\cdots u_{\lceil \frac{n}{2}\rceil -2}{u}_{\lceil \frac{n}{2}\rceil -1}{u}_{\lceil \frac{n}{2}\rceil }{v}_{\lfloor \frac{n}{2}\rfloor }{v}_{\lfloor \frac{n}{2}\rfloor -1}{v}_{\lfloor \frac{n}{2}\rfloor -2}\cdots v_3{v}_2{v}_1.$$

The following Figure 1 shows the case where $P_n$ has an odd order n.

For the linear forest $m{P}_3\bigcup P_n$, where $m\ge 2$ and $n\ge m+4$, we define a function f on $E(m{P}_3\bigcup P_n)$ as follows:

$${\displaystyle \left\{\begin{array}{cc}f(x_{2i-1}{z}_{2i-1})=6(i-1)+1,\hfill & 1\le i\le \lceil \frac{m}{2}\rceil ,\hfill \\ f(z_{2i-1}{y}_{2i-1})=6(i-1)+2,\hfill & 1\le i\le \lceil \frac{m}{2}\rceil ,\hfill \\ f(x_{2i}{z}_{2i})=6(i-1)+4,\hfill & 1\le i\le \lfloor \frac{m}{2}\rfloor ,\hfill \\ f(z_{2i}{y}_{2i})=6(i-1)+5,\hfill & 1\le i\le \lfloor \frac{m}{2}\rfloor ,\hfill \\ f(u_i{u}_{i+1})=6(i-1)+3,\hfill & 1\le i\le \lfloor \frac{m}{2}\rfloor ,\hfill \\ f(v_i{v}_{i+1})=6(i-1)+6,\hfill & 1\le i\le \lfloor \frac{m}{2}\rfloor ,\hfill \\ f(u_{\lfloor \frac{m}{2}\rfloor +1}{u}_{\lfloor \frac{m}{2}\rfloor +2})=2m+2\lfloor \frac{m}{2}\rfloor +1,\hfill & \\ f(u_i{u}_{i+1})+1=f(v_i{v}_{i+1}),\hfill & \lfloor \frac{m}{2}\rfloor +1\le i\le \lfloor \frac{n}{2}\rfloor -1,\hfill \\ f(v_i{v}_{i+1})+1=f(u_{i+1}{u}_{i+2}),\hfill & \lfloor \frac{m}{2}\rfloor +1\le i\le \lfloor \frac{n}{2}\rfloor -1,\mathrm{but} i\ne \frac{n}{2}-1,\hfill \\ f(u_{\lceil \frac{n}{2}\rceil }{v}_{\lfloor \frac{n}{2}\rfloor })=2m+n-1.\hfill \end{array}\right.}$$

We see that

$$({\displaystyle \bigcup _{i=1}^m}\{f(x_i{z}_i),f(z_i{y}_i)\})\bigcup ({\displaystyle \bigcup _{i=1}^{\lfloor \frac{m}{2}\rfloor }}\{f(u_i{u}_{i+1}),f(v_i{v}_{i+1})\})=\{1,2,\cdots ,2m+2\lfloor \frac{m}{2}\rfloor \},$$

and

$$\begin{array}{ccc}& & ({\displaystyle \bigcup _{i=\lfloor \frac{m}{2}\rfloor +1}^{\lceil \frac{n}{2}\rceil -1}}\{f(u_i{u}_{i+1})\})\bigcup ({\displaystyle \bigcup _{i=\lfloor \frac{m}{2}\rfloor +1}^{\lfloor \frac{n}{2}\rfloor -1}}\{f(v_i{v}_{i+1})\})\bigcup \{f(u_{\lceil \frac{n}{2}\rceil }{v}_{\lfloor \frac{n}{2}\rfloor })\}\hfill \\ & =& \{2m+2\lfloor \frac{m}{2}\rfloor +1,2m+2\lfloor \frac{m}{2}\rfloor +2,\cdots ,2m+n-1\}.\hfill \end{array}$$

That is, $f:E(m{P}_3\bigcup P_n)\to \{1,2,\cdots ,2m+n-1\}$ is an edge labeling of $m{P}_3\bigcup P_n$. From the labeling f the following is observed: $f^{+}(x_{2i-1})\equiv 1mod6$, $f^{+}(y_{2i-1})\equiv 2mod6$, $f^{+}(x_{2i})\equiv 4mod6$, $f^{+}(y_{2i})$ $\equiv 5mod6$ and $f^{+}(z_i)\equiv 3mod6$. And $f^{+}(u_i)\equiv f^{+}(v_j)\equiv 0mod6$ if $i,j\le \lfloor \frac{m}{2}\rfloor$ except for $f^{+}(u_1)=3$. This labeling strategy helps vertices of $m{P}_3\bigcup P_n$ obtaining distinct vertex sums with an only exception. As an example, for the linear forest $7P_3\bigcup P_{11}$, Figure 2 shows the edge labels and vertex sums under f. We note that the number beside an edge is the label of this edge, and the number above a vertex is the induced vertex sum of this vertex.

In Figure 2, we see that the induced vertex sums of all vertices in $7P_3\bigcup P_{11}$ are almost distinct, except for $f^{+}(z_1)=f^{+}(u_1)=3$. Therefore, we have the following lemma.

Lemma 1.

Suppose that f is the aforementioned edge labeling of the linear forest $m{P}_3\bigcup P_n$, where $m\ge 2$ and $n\ge m+4$. Then, for any pair of distinct vertices x and y in $m{P}_3\bigcup P_n$, we have $f^{+}(x)\ne f^{+}(y)$, except for $f^{+}(z_1)=f^{+}(u_1)=3$.

Proof. 

We first consider the case of $m\ge 4$. According to the definition of f, we have the following.

(i)

$f^{+}(z_1)=f^{+}(u_1)=3$.

(ii)

$f^{+}(x_{2i-1})\equiv 1mod6$, $f^{+}(y_{2i-1})\equiv 2mod6$, $f^{+}(x_{2i})\equiv 4mod6$, $f^{+}(y_{2i})$$\equiv 5mod6$, and $f^{+}(x_1)<f^{+}(y_1)<f^{+}(x_2)<f^{+}(y_2)<\cdots <f^{+}(x_m)<f^{+}(y_m)$.

(iii)

$f^{+}(z_{2i-1})=6(2i-2)+3$, $f^{+}(z_{2i})=6(2i-1)+3$. That is, $f^{+}(z_j)\equiv 3mod6$, and $f^{+}(z_1)<f^{+}(z_2)<\cdots <f^{+}(z_m)$.

(iv)

For $2\le i\le \lfloor \frac{m}{2}\rfloor$, we have $f^{+}(u_i)=6(2i-2)$ and $f^{+}(v_i)=6(2i-1)$. That is, for $2\le i,j\le \lfloor \frac{m}{2}\rfloor$, $f^{+}(u_i)\equiv f^{+}(v_j)\equiv 0mod6$. In addition, for $f^{+}(v_{\lfloor \frac{m}{2}\rfloor })=12\lfloor \frac{m}{2}\rfloor -6$, $f^{+}(u_{\lfloor \frac{m}{2}\rfloor +1})=2m+8\lfloor \frac{m}{2}\rfloor -2$, we see that $f^{+}(v_{\lfloor \frac{m}{2}\rfloor })<f^{+}(u_{\lfloor \frac{m}{2}\rfloor +1})$. Then, we have $6=f^{+}(v_1)<f^{+}(u_2)<f^{+}(v_2)<f^{+}(u_3)<f^{+}(v_3)<\cdots <f^{+}(u_{\lfloor \frac{m}{2}\rfloor })<f^{+}(v_{\lfloor \frac{m}{2}\rfloor })<f^{+}(u_{\lfloor \frac{m}{2}\rfloor +1})$. Further, it is evident that $f^{+}(u_{\lfloor \frac{m}{2}\rfloor +1})<f^{+}(v_{\lfloor \frac{m}{2}\rfloor +1})<f^{+}(u_{\lfloor \frac{m}{2}\rfloor +2})<f^{+}(v_{\lfloor \frac{m}{2}\rfloor +2})<\cdots <f^{+}(u_{\lfloor \frac{n}{2}\rfloor })<f^{+}(v_{\lfloor \frac{n}{2}\rfloor })$. And $f^{+}(v_{\lfloor \frac{n}{2}\rfloor })<f^{+}(u_{\lceil \frac{n}{2}\rceil })$ if n is odd.

Now, let ${\displaystyle A={\displaystyle \bigcup _{i=1}^m}\{x_i,y_i,z_i\}}$, ${\displaystyle B=\{v_1\}\bigcup ({\displaystyle \bigcup _{i=2}^{\lfloor \frac{m}{2}\rfloor }}\{u_i,v_i\})}$, and ${\displaystyle C=({\displaystyle \bigcup _{i=\lfloor \frac{m}{2}\rfloor +1}^{\lceil \frac{n}{2}\rceil }}\{u_i\})\bigcup }$ ${\displaystyle ({\displaystyle \bigcup _{j=\lfloor \frac{m}{2}\rfloor +1}^{\lfloor \frac{n}{2}\rfloor }}\{v_j\})}$. We see that A, B, and C are subsets of $V(m{P}_3\bigcup P_n)$, and $A\bigcup B\bigcup C=V(m{P}_3\bigcup P_n)-\{u_1\}$. According to (ii)∼(iv) above, it can be seen that $f^{+}(u)$ are distinct for all $u\in A\bigcup B$, and $f^{+}(v)$ are distinct for all $v\in B\bigcup C$. To show that this lemma holds, it suffices to show that $f^{+}(A)\bigcap f^{+}(C)=\varphi$. We distinguish the following two subcases: m is odd and m is even.

Subcase 1: m is odd. We evaluate $f^{+}(z_{m-1}),f^{+}(z_m),f^{+}(u_{\lfloor \frac{m}{2}\rfloor +1})$, and $f^{+}(v_{\lfloor \frac{m}{2}\rfloor +1})$. $f^{+}(z_{m-1})=f(x_{m-1}{z}_{m-1})+f(z_{m-1}{y}_{m-1})=6(\frac{m-1}{2}-1)+4+6(\frac{m-1}{2}-1)+5=6m-9$. $f^{+}(z_m)=f(x_m{z}_m)+f(z_m{y}_m)=6(\frac{m+1}{2}-1)+1+6(\frac{m+1}{2}-1)+2=6m-3$, and $f^{+}(u_{\lfloor \frac{m}{2}\rfloor +1})=2m+8\lfloor \frac{m}{2}\rfloor -2=6m-6$, and $f^{+}(v_{\lfloor \frac{m}{2}\rfloor +1})=2m+8\lfloor \frac{m}{2}\rfloor +2=6m-2$. It can be seen that $f^{+}(z_{m-1}),f^{+}(z_m)$ are the two greatest numbers in the set $f^{+}(A)$, and $f^{+}(u_{\lfloor \frac{m}{2}\rfloor +1}),f^{+}(v_{\lfloor \frac{m}{2}\rfloor +1})$ are the two least numbers in the set $f^{+}(C)$. As $f^{+}(z_{m-1})<f^{+}(u_{\lfloor \frac{m}{2}\rfloor +1})<f^{+}(z_m)<f^{+}(v_{\lfloor \frac{m}{2}\rfloor +1})$, we have $f^{+}(A)\bigcap f^{+}(C)=\varphi$.

Subcase 2: m is even. We evaluate $f^{+}(z_m)$ and $f^{+}(u_{\lfloor \frac{m}{2}\rfloor +1})$. $f^{+}(z_m)=f(x_m{z}_m)+f(z_m{y}_m)=6(\frac{m}{2}-1)+4+6(\frac{m}{2}-1)+5=6m-3$, and $f^{+}(u_{\lfloor \frac{m}{2}\rfloor +1})=2m+8\lfloor \frac{m}{2}\rfloor -2=6m-2$. It can be seen that $f^{+}(z_m)$ is the greatest number in $f^{+}(A)$, and $f^{+}(u_{\lfloor \frac{m}{2}\rfloor +1})$ is the least number in $f^{+}(C)$. As $f^{+}(z_m)<f^{+}(u_{\lfloor \frac{m}{2}\rfloor +1})$, we have $f^{+}(A)\bigcap f^{+}(C)=\varphi$.

From the two subcases we see that $f^{+}(A)\bigcap f^{+}(C)=\varphi$. Thus the lemma holds for the case of $m\ge 4$.

The cases $m=2$ and $m=3$ are shown in the following figures (Figure 3 and Figure 4).

The proof for this part is simple, we leave it to the readers. □

In the following lemma, we modify the labeling f stated in Lemma 1 to obtain an antimagic labeling for the linear forest $m{P}_3\bigcup P_n$, where $m\ge 4$ and $n\ge m+5$.

Lemma 2.

For $m\ge 4$ and $n\ge m+5$, linear forest $m{P}_3\bigcup P_n$ is antimagic.

Proof. 

Let f be the edge labeling of $m{P}_3\bigcup P_n$ which is defined as in Lemma 1. Recall that $P_n$ is the path $u_1{u}_2{u}_3\cdots u_{\lceil \frac{n}{2}\rceil }{v}_{\lfloor \frac{n}{2}\rfloor }\cdots v_3{v}_2{v}_1$. We distinguish the two cases $m=2k+1$ and $m=2k$, where $k\ge 2$.

Case 1. $m=2k+1$ and $k\ge 2$. In this case, we see that $\lfloor \frac{n}{2}\rfloor \ge k+3$. Now, we define a function $f_1$ on $E(m{P}_3\bigcup P_n)$ as

$$\left\{\begin{array}{c}{f}_1(x_1{z}_1)=f(u_{k+2}{u}_{k+3})=6k+5,\hfill \\ f_1(u_{k+2}{u}_{k+3})=f(x_1{z}_1)=1,\hfill \\ f_1(e)=f(e)\mathrm{for} \mathrm{every} \mathrm{other} \mathrm{edge} e.\hfill \end{array}\right.$$

Evidently, $f_1$ is an edge labeling of $m{P}_3\bigcup P_n$, and $f_1^{+}(x)=f^{+}(x)$ for all $x\in V(m{P}_3\bigcup P_n)-\{x_1,z_1,u_{k+2},u_{k+3}\}$. Let $P=\{x_1,z_1,u_{k+2},u_{k+3}\}$, and $Q=V(m{P}_3\bigcup P_n)-P$. According to Lemma 1, $f_1^{+}(x)$ are distinct for all $x\in Q$. Now, we evaluate $f_1^{+}(y)$ for all $y\in P$. Note that $f_1(u_{k+1}{u}_{k+2})=6k+3$ and $f_1(u_{k+3}{u}_{k+4})=6k+7$, or $f_1(u_{k+3}{v}_{k+3})=6k+7$ if $n=2k+6$. Then, $f_1^{+}(x_1)=f_1(x_1{z}_1)=6k+5$, $f_1^{+}(z_1)=f_1(x_1{z}_1)+f_1(z_1{y}_1)=(6k+5)+2=6k+7$, $f_1^{+}(u_{k+2})=f_1(u_{k+1}{u}_{k+2})+f_1(u_{k+2}{u}_{k+3})=(6k+3)+1=6k+4$, and $f_1^{+}(u_{k+3})=f_1(u_{k+2}{u}_{k+3})+f_1(u_{k+3}{u}_{k+4})$ (or $f_1(u_{k+3}{v}_{k+3})$) $=1+(6k+7)=6k+8$. It is observed that $f_1^{+}(y)$ are distinct for all $y\in P$. To show that $f_1^{+}(x)$ are distinct for all $x\in V(m{P}_3\bigcup P_n)$, it suffices to show that $f_1^{+}(P)\bigcap f_1^{+}(Q)=\varphi$. Firstly, we divide Q into two parts, A and B, where $A=\{y_1\}\bigcup ({\bigcup }_{i=2}^{2k+1}\{x_i,y_i,z_i\})\bigcup ({\bigcup }_{i=1}^k\{u_i,v_i\})$ and $B=Q-A$. We now claim that $f_1^{+}(P)\bigcap f_1^{+}(A)=\varphi$. From the proof of Lemma 1, it can be seen that the values $f_1^{+}(x_{2k+1})=6k+1$, $f_1^{+}(y_{2k+1})=6k+2$, $f_1^{+}(x_{2k})=6k-2$, and $f_1^{+}(y_{2k})=6k-1$ are the greatest numbers in $f_1^{+}(A)$ congruent to 1, 2, 4, and 5 modulo 6, respectively. As $f_1^{+}(z_1)\equiv 1mod6$ and $f_1^{+}(z_1)>f_1^{+}(x_{2k+1})$, $f_1^{+}(u_{k+3})\equiv 2mod6$ and $f_1^{+}(u_{k+3})>f_1^{+}(y_{2k+1})$, $f_1^{+}(u_{k+2})\equiv 4mod6$ and $f_1^{+}(u_{k+2})>f_1^{+}(x_{2k})$, and $f_1^{+}(x_1)\equiv 5mod6$ and $f_1^{+}(x_1)>f_1^{+}(y_{2k})$, we have $f_1^{+}(P)\bigcap f_1^{+}(A)=\varphi$. Next, we claim that $f_1^{+}(P)\bigcap f_1^{+}(B)=\varphi$. Evidently, $f_1^{+}(u_{k+1})=f_1(u_k{u}_{k+1})+f_1(u_{k+1}{u}_{k+2})=(6k-3)+(6k+3)=12k$ is the least number in $f_1^{+}(B)$, and $f_1^{+}(u_{k+3})=6k+8$ is the greatest number in $f_1^{+}(P)$. As $f_1^{+}(u_{k+1})>f_1^{+}(u_{k+3})$ when $k\ge 2$, we have $f_1^{+}(P)\bigcap f_1^{+}(B)=\varphi$. Thus, $f_1^{+}(P)\bigcap f_1^{+}(Q)=\varphi$.

Case 2. $m=2k$ and $k\ge 2$. In this case, we see that $\lceil \frac{n}{2}\rceil \ge k+3$ and $\lfloor \frac{n}{2}\rfloor \ge k+2$. Now, we define a function $f_2$ on $E(m{P}_3\bigcup P_n)$ as

$$\left\{\begin{array}{c}{f}_2(x_1{z}_1)=f(v_{k+1}{v}_{k+2})=6k+2,\hfill \\ f_2(v_{k+1}{v}_{k+2})=f(x_1{z}_1)=1,\hfill \\ f_2(e)=f(e)\mathrm{for} \mathrm{every} \mathrm{other} \mathrm{edge} e.\hfill \end{array}\right.$$

Evidently, $f_2$ is an edge labeling of $m{P}_3\bigcup P_n$, and $f_2^{+}(x)=f^{+}(x)$ for all $x\in V(m{P}_3\bigcup P_n)-\{x_1,z_1,v_{k+1},v_{k+2}\}$. Let $P=\{x_1,z_1,v_{k+1},v_{k+2}\}$, and $Q=V(m{P}_3\bigcup P_n)-P$. According to Lemma 1, $f_2^{+}(x)$ are distinct for all $x\in Q$. Now, we evaluate $f_2^{+}(y)$ for all $y\in P$. Note that $f_2(v_k{v}_{k+1})=6k$ and $f_2(v_{k+2}{v}_{k+3})=6k+4$, or $f_2(v_{k+2}{u}_{k+3})=6k+4$ if $n=2k+5$. Then, $f_2^{+}(x_1)=f_2(x_1{z}_1)=6k+2$, $f_2^{+}(z_1)=f_2(x_1{z}_1)+f_2(z_1{y}_1)=(6k+2)+2=6k+4$, $f_2^{+}(v_{k+1})=f_2(v_k{v}_{k+1})+f_2(v_{k+1}{v}_{k+2})=6k+1$, and $f_2^{+}(v_{k+2})=f_2(v_{k+1}{v}_{k+2})+f_2(v_{k+2}{v}_{k+3})$ (or $f_2(v_{k+2}{u}_{k+3})) =1+(6k+4)=6k+5$. It is observed that $f_2^{+}(y)$ are distinct for all $y\in P$. To show that $f_2^{+}(x)$ are distinct for all $x\in V(m{P}_3\bigcup P_n)$, it suffices to show that $f_2^{+}(P)\bigcap f_2^{+}(Q)=\varphi$. Firstly, we divide Q into two parts, A and B, where $A=\{y_1\}\bigcup ({\bigcup }_{i=2}^{2k}\{x_i,y_i,z_i\})\bigcup ({\bigcup }_{i=1}^k\{u_i,v_i\})$ and $B=Q-A$. We now claim that $f_2^{+}(P)\bigcap f_2^{+}(A)=\varphi$. From the proof of Lemma 1, it can be seen that the values $f_2^{+}(x_{2k-1})=6k-5$, $f_2^{+}(y_{2k-1})=6k-4$, $f_2^{+}(x_{2k})=6k-2$, and $f_2^{+}(y_{2k})=6k-1$ are the greatest numbers in $f_2^{+}(A)$ congruent to 1, 2, 4, and 5 modulo 6, respectively. As $f_2^{+}(v_{k+1})\equiv 1mod6$ and $f_2^{+}(v_{k+1})>f_2^{+}(x_{2k-1})$, $f_2^{+}(x_1)\equiv 2mod6$ and $f_2^{+}(x_1)>f_2^{+}(y_{2k-1})$, $f_2^{+}(z_1)\equiv 4mod6$ and $f_2^{+}(z_1)>f_2^{+}(x_{2k})$, and $f_2^{+}(v_{k+2})\equiv 5mod6$ and $f_2^{+}(v_{k+2})>f_2^{+}(y_{2k})$, we have $f_2^{+}(P)\bigcap f_2^{+}(A)=\varphi$. Next, we claim that $f_2^{+}(P)\bigcap f_2^{+}(B)=\varphi$. Evidently, $f_2^{+}(u_{k+1})=f_2(u_k{u}_{k+1})+f_2(u_{k+1}{u}_{k+2})=(6k-3)+(6k+1)=12k-2$ is the least number in $f_2^{+}(B)$, and $f_2^{+}(v_{k+2})=6k+5$ is the greatest number in $f_2^{+}(P)$. As $f_2^{+}(u_{k+1})>f_2^{+}(v_{k+2})$ when $k\ge 2$, we have $f_2^{+}(P)\bigcap f_2^{+}(B)=\varphi$. Thus, $f_2^{+}(P)\bigcap f_2^{+}(Q)=\varphi$.

The above two cases show that the linear forest $m{P}_3\bigcup P_n$ has an antimagic labeling. Hence, $m{P}_3\bigcup P_n$ is antimagic. □

The following lemma shows that the linear forest $m{P}_3\bigcup P_{m+4}$ ($m\ge 2$) also has an antimagic labeling.

Lemma 3.

For $m\ge 2$, linear forest $m{P}_3\bigcup P_{m+4}$ is antimagic.

Proof. 

Let f be the edge labeling of $m{P}_3\bigcup P_{m+4}$ which is defined as in Lemma 1. We distinguish the two cases $m=2k+1$ and $m=2k$, where $k\in N$.

Case 1. $m=2k+1$. In this case, $P_{m+4}$ is the path $u_1{u}_2\cdots u_{k+2}{u}_{k+3}{v}_{k+2}{v}_{k+1}\cdots v_2{v}_1$. Now, we define a function $f_1$ on $E(m{P}_3\bigcup P_{m+4})$ as

$$\left\{\begin{array}{c}{f}_1(z_1{y}_1)=f(v_{k+2}{v}_{k+1})=6k+4,\hfill \\ f_1(v_{k+2}{v}_{k+1})=f(u_{k+3}{v}_{k+2})=6k+6,\hfill \\ f_1(u_{k+3}{v}_{k+2})=f(z_1{y}_1)=2,\hfill \\ f_1(e)=f(e)\mathrm{for} \mathrm{every} \mathrm{other} \mathrm{edge} e.\hfill \end{array}\right.$$

Evidently, $f_1$ is an edge labeling of $m{P}_3\bigcup P_{m+4}$, and $f_1^{+}(x)=f^{+}(x)$ for all $x\in V(m{P}_3\bigcup P_{m+4})-\{y_1,z_1,u_{k+3},v_{k+2},v_{k+1}\}$. Let $P=\{y_1,z_1,u_{k+1},$ $u_{k+2},u_{k+3},v_{k+2},v_{k+1}\}$, and $Q=V(m{P}_3\bigcup P_{m+4})-P$. According to Lemma 1, $f_1^{+}(x)$ are distinct for all $x\in Q$. Now, we evaluate $f_1^{+}(y)$ for all $y\in P$. We see that $f_1^{+}(y_1)=f_1(z_1{y}_1)=6k+4$, $f_1^{+}(z_1)=f_1(x_1{z}_1)+f_1(z_1{y}_1)=1+(6k+4)=6k+5$, $f_1^{+}(u_{k+1})=f_1(u_k{u}_{k+1})+f_1(u_{k+1}{u}_{k+2})=(6k-3)+(6k+3)=12k$, $f_1^{+}(u_{k+2})=f_1(u_{k+1}{u}_{k+2})+f_1(u_{k+2}{u}_{k+3})=(6k+3)+(6k+5)=12k+8$, $f_1^{+}(u_{k+3})=f_1(u_{k+2}{u}_{k+3})+f_1(u_{k+3}{v}_{k+2})=(6k+5)+2=6k+7$, $f_1^{+}(v_{k+2})=f_1(u_{k+3}{v}_{k+2})+f_1(v_{k+2}{v}_{k+1})=2+(6k+6)=6k+8$, and $f_1^{+}(v_{k+1})=f_1(v_{k+2}{v}_{k+1})+f_1(v_{k+1}{v}_k)=(6k+6)+6k=12k+6$. It is observed that $f_1^{+}(y)$ are distinct for all $y\in P$. To show that $f_1^{+}(x)$ are distinct for all $x\in V(m{P}_3\bigcup P_{m+4})$, it suffices to show that $f_1^{+}(P)\bigcap f_1^{+}(Q)=\varphi$. From the proof of Lemma 1, it can be seen that the values $f_1^{+}(x_{2k+1})=6k+1$, $f_1^{+}(y_{2k+1})=6k+2$, $f_1^{+}(x_{2k})=6k-2$, $f_1^{+}(y_{2k})=6k-1$, and $f_1^{+}(v_k)=12k-6$ are the greatest numbers in $f_1^{+}(Q)$ congruent to 1, 2, 4, 5, and 0 modulo 6, respectively. As $f_1^{+}(u_{k+3})\equiv 1mod6$ and $f_1^{+}(u_{k+3})>f_1^{+}(x_{2k+1})$, $f_1^{+}(u_{k+2})\equiv f_1^{+}(v_{k+2})\equiv 2mod6$ and $f_1^{+}(u_{k+2})>f_1^{+}(v_{k+2})>f_1^{+}(y_{2k+1})$, $f_1^{+}(y_1)\equiv 4mod6$ and $f_1^{+}(y_1)>f_1^{+}(x_{2k})$, $f_1^{+}(z_1)\equiv 5mod6$ and $f_1^{+}(z_1)>f_1^{+}(y_{2k})$, and $f_1^{+}(v_{k+1})\equiv f_1^{+}(u_{k+1})\equiv 0mod6$ and $f_1^{+}(v_{k+1})>f_1^{+}(u_{k+1})>f_1^{+}(v_k)$, we have $f_1^{+}(P)\bigcap f_1^{+}(Q)$ $=\varphi$.

Case 2. $m=2k$. In this case, $P_{m+4}$ is the path $u_1{u}_2\cdots u_{k+1}{u}_{k+2}{v}_{k+2}{v}_{k+1}\cdots v_2{v}_1$. Now, we define a function $f_2$ on $E(m{P}_3\bigcup P_{m+4})$ as

$$\left\{\begin{array}{c}{f}_2(z_1{y}_1)=f(u_{k+1}{u}_{k+2})=6k+1,\hfill \\ f_2(u_{k+1}{u}_{k+2})=f(u_{k+2}{v}_{k+2})=6k+3,\hfill \\ f_2(u_{k+2}{v}_{k+2})=f(z_1{y}_1)=2,\hfill \\ f_2(e)=f(e)\mathrm{for} \mathrm{every} \mathrm{other} \mathrm{edge} e.\hfill \end{array}\right.$$

Evidently, $f_2$ is an edge labeling of $m{P}_3\bigcup P_{m+4}$, and $f_2^{+}(x)=f^{+}(x)$ for all $x\in V(m{P}_3\bigcup P_{m+4})-\{y_1,z_1,u_{k+1},u_{k+2},v_{k+2}\}$. It is observed that if $k=1$, $f_2$ is an antimagic labeling of $2P_3\bigcup P_6$. In the following, we consider the case of $k\ge 2$. Let $P=\{y_1,z_1,u_{k+1},u_{k+2},v_{k+2},v_{k+1}\}$, and $Q=V(m{P}_3\bigcup P_{m+4})-P$. According to Lemma 1, $f_2^{+}(x)$ are distinct for all $x\in Q$. Now, we evaluate $f_2^{+}(y)$ for all $y\in P$. We see that $f_2^{+}(y_1)=f_2(z_1{y}_1)=6k+1$, $f_2^{+}(z_1)=f_2(x_1{z}_1)+f_2(z_1{y}_1)=1+(6k+1)=6k+2$, $f_2^{+}(u_{k+1})=f_2(u_k{u}_{k+1})+f_2(u_{k+1}{u}_{k+2})=(6k-3)+(6k+3)=12k$, $f_2^{+}(u_{k+2})=f_2(u_{k+1}{u}_{k+2})+f_2(u_{k+2}{v}_{k+2})=(6k+3)+2=6k+5$, $f_2^{+}(v_{k+2})=f_2(u_{k+2}{v}_{k+2})+f_2(v_{k+2}{v}_{k+1})=2+(6k+2)=6k+4$, and $f_2^{+}(v_{k+1})=f_2(v_{k+2}{v}_{k+1})+f_2(v_{k+1}{v}_k)=(6k+2)+6k=12k+2$. It is observed that $f_2^{+}(y)$ are distinct for all $y\in P$. To show that $f_2^{+}(x)$ are distinct for all $x\in V(m{P}_3\bigcup P_{m+4})$, it suffices to show that $f_2^{+}(P)\bigcap f_2^{+}(Q)=\varphi$. From the proof of Lemma 1, it can be seen that the values $f_2^{+}(x_{2k-1})=6k-5$, $f_2^{+}(y_{2k-1})=6k-4$, $f_2^{+}(x_{2k})=6k-2$, $f_2^{+}(y_{2k})=6k-1$, and $f_2^{+}(v_k)=12k-6$ are the greatest numbers in $f_2^{+}(Q)$ congruent to 1, 2, 4, 5, and 0 modulo 6, respectively. As $f_2^{+}(y_1)\equiv 1mod6$ and $f_2^{+}(y_1)>f_2^{+}(x_{2k-1})$, $f_2^{+}(v_{k+1})\equiv f_2^{+}(z_1)\equiv 2mod6$ and $f_2^{+}(v_{k+1})>f_2^{+}(z_1)>f_2^{+}(y_{2k-1})$, $f_2^{+}(v_{k+2})\equiv 4mod6$ and $f_2^{+}(v_{k+2})$ $>f_2^{+}(x_{2k})$, $f_2^{+}(u_{k+2})\equiv 5mod6$ and $f_2^{+}(u_{k+2})>f_2^{+}(y_{2k})$, and $f_2^{+}(u_{k+1})\equiv 0mod6$ and $f_2^{+}(u_{k+1})>f_2^{+}(v_k)$, we have $f_2^{+}(P)\bigcap f_2^{+}(Q)=\varphi$.

The above two cases show that the linear forest $m{P}_3\bigcup P_{m+4}$ has an antimagic labeling. Thus, $m{P}_3\bigcup P_{m+4}$ is antimagic. □

According to Lemmas 2 and 3, we have the following theorem.

Theorem 2.

For $m\ge 4$ and $n\ge m+4$, linear forest $m{P}_3\bigcup P_n$ is antimagic.

3. Conclusions

Theorem 2 states that linear forest $m{P}_3\bigcup P_n$ is antimagic for $4\le m\le n-4$ and $n\ge 8$. According to Theorem 1 for $n\ge 4$ if $m{P}_3\bigcup P_n$ is antimagic then ${\displaystyle m\le \frac{2n-7+\sqrt{8n^2-40n+49}}{2}}$. It is seen that there is a gap between $n-4$ and ${\displaystyle \frac{2n-7+\sqrt{8n^2-40n+49}}{2}}$. We would like to know if the upper bound $n-4$ for m in Theorem 2 can be raised. To conclude this study, the following problems are proposed. The first one is previously mentioned in Section 1.

Problem 1.

How many disjoint paths $P_3$ can be added to a $P_2,P_3$-free linear forest such that the extended new linear forest is still antimagic?

Problem 2.

What are the necessary and sufficient conditions for linear forest $m{P}_3\bigcup P_n$ to be antimagic?