Injective edge coloring of generalized Petersen graphs

1.   Introduction

Let $G$ be a finite and simple graph. We use $V(G)$, $E(G)$ and $\Delta(G)$ to denote its vertex set, edge set and maximum degree, respectively. A $proper\ vertex\; (edge)\ coloring$ is a mapping from the vertex (edge) set to a finite set of colors, such that adjacent vertices (edges) receive distinct colors. A $k$-$injective\ coloring$ of a graph $G$ is a mapping $\psi :V(G)\rightarrow \{1, 2, \dots, k\}$, such that if two vertices have a common neighbor, then they receive distinct colors. The $injective\ chromatic\ number$ of $G$, denoted by $\chi_{i}(G)$, is the minimum $k$ for which $G$ has a $k$-injective coloring. The injective coloring of graphs was originated from the Complexity Theory on Random Access Machines, which was proposed by Hahn et al. ^[8] and applied to the theory of error correcting codes and the designing of computer networks ^[2].

Similarly, Cardoso et al. ^[6] introduced the concept of injective edge coloring, motivated by a Packet Radio Network problem. Three edges $e_1$, $e_2$ and $e_3$ in a graph $G$ are $consecutive$ if they form a cycle of length $3$ or a path in this order. A $k$-$injective\ edge \ coloring$ of a graph $G$ is a mapping $\psi :E(G)\rightarrow \{1, 2, \dots, k\}$, such that if $e_1$, $e_2$, $e_3$ are consecutive, then $\psi(e_1)\neq\psi(e_3)$. If there is a $k$-injective edge coloring of $G$, then we say that $G$ is $k$-$injective\; edge\; colored$. The minimum $k$ for which $G$ has a $k$-injective edge coloring is called the $injective\ edge\ coloring\ number$ of $G$, denoted by $\chi_{i}^{'}(G)$.

Cardoso et al. ^[6] showed that it is NP-complete to decide whether $\chi_{i}^{'}(G) = k$. They determined the injective edge coloring numbers for paths, cycles, complete bipartite graphs, and Petersen graph, and they also gave bounds on some other classes of graphs.

Proposition 1.1 (^[6]). Let $P_n\; (C_n)$ be a path (cycle) of order $n$, $K_{p, q}$ be a complete bipartite graph, and $P$ be the Petersen graph. Then

● $\chi_i^{'}(P_n) = 2, \; for\, n \geq4.$

● $\chi_i^{'}(C_n) = \left\{\begin{array}{rcl}2&if\, n\equiv0\; (mod\; 4), \\ 3 &otherwise.\end{array}\right.$

● $\chi_i^{'}(K_{p, q}) = min\{p, q\}.$

● $\chi_i^{'}(\mathit{P}) = 5$.

A graph $G$ is an $\omega'\; edge\; injective\; colorable\; (perfect\; EIC-)\; graph$ if $\chi_i^{'}(G) = \omega'(G)$, where $\omega'(G)$ is the number of edges in a maximum clique of $G$. In ^[11], Yue et al. constructed some perfect EIC-graphs, and gave a sharp bound of the injective edge coloring number of a $2$-connected graph with some forbidden conditions. Bu and Qi ^[5] and Ferdjallah ^[7] studied the injective edge coloring of sparse graphs in terms of the maximum average degree. Kostochka ^[9] studied the injective edge coloring in terms of the maximum degree. Recently, in ^[3,4], Bu et al. presented some results on the injective edge coloring numbers of planar graphs. In this paper, we will consider the injective edge coloring of generalized Petersen graphs.

For positive integers $n$ and $k$, where $n\geq 3$ and $1\leq k < \frac{n}{2}$, $the\; generalized\; Petersen\; graph$ $P(n, k)$ is a graph with vertex set $V = \{u_1, u_2, \dots, u_n; v_1, v_2, \dots, v_n\}$ and edge set $E = \{u_{i}u_{i+1}, \; u_{i}v_i, \; v_iv_{i+k}|\; i\in\{1, 2, \ldots, n\}, \; the\; subscripts\; are\; taken\; modulo\; n\}.$} We denote $u_1, u_2, \dots, u_n$ as outer vertices and $v_1, v_2, \ldots, v_n$ as inner vertices. The edges $u_{i}u_{i+1}$, $v_iv_{i+k}$, and $u_{i}v_i$ are denoted as outer edges, inner edges and leg edges, respectively, where $i\in \{1, 2, ..., n\}$. Generalized Petersen graphs are being analyzed extensively because of their applications. There have been some results about the colorings of generalized Petersen graphs, see in ^[1,10,12].

Here we consider the injective edge colorings of generalized Petersen graphs $P(n, k)$ for $k = 1$ and $k = 2$. We prove the following theorems:

Theorem 1.1. If $n\geq 6$, then we have that

Moreover, $\chi_i^{'}(P(3, 1)) = 6$, $\chi_i^{'}(P(4, 1)) = 4, \; \chi_i^{'}(P(5, 1)) = 5.$

Theorem 1.2. If $n\geq 8,$ then $4\leq \chi_{i}^{'}(P(n, 2))\leq 5.$ Moreover, $\chi_i^{'}(P(4, 2)) = 4$, $\chi_i^{'}(P(5, 2)) = \chi_i^{'}(P(6, 2)) = \chi_i^{'}(P(7, 2)) = 5.$

The paper is organized as follows. The exact values of the injective edge coloring numbers of $P(n, 1)$ are presented in Section 2. In Section 3, we estimate the injective edge coloring numbers of $P(n, 2)$.

2.   Injective edge coloring of $P(n, 1)$

In this section, we determine $\chi_{i}^{'}(P(n, 1))$ for $n\ge 3$. The graph $P(n, 1)$ is shown in Figure 1. We denote the cycle $u_1u_2...u_n$ as outer cycle, and the cycle $v_1v_2...v_n$ as inner cycle. We say that an edge $e_1$ $sees$ an edge $e_2$, if there is an edge $e$ such that $e_1, \; e, \; e_2$ are consecutive. A $labelling$ of $P(n, 1)$ is a mapping $L$ from vertices of $P(n, 1)$ to a set $\{1, 2, ..., k\}$.

We need a proposition posed by Cardoso et al. ^[6].

Proposition 2.1 (^[6]). If H is a subgraph of a connected graph G, then $\chi_{i}^{'}(H)\le \chi_{i}^{'}(G).$

By this proposition, we have the following lemma.

Lemma 2.1. If $n\ge 3$, then $\chi_{i}^{'}(P(n, 1))\ge3$.

Proof. Since the edges $u_1u_2, u_2u_3, u_3v_3, v_3v_2, v_2v_1, v_1u_1$ form a cycle of length $6$, $C_6$ is a subgraph of $P(n, 1)$. By Proposition 1.1 and Proposition 2.1, we have that $\chi_{i}^{'}(P(n, 1))\geq3$.

Lemma 2.2. For $n \geq 6$, $\chi_{i}^{'}(P(n, 1)) = 3$ if and only if $n$ is a multiple of $6$.

Proof. Suppose that $P(n, 1)$ has an injective edge coloring $\psi$ using only three colors $1$, $2$ and $3$. Let $C = v_1v_2v_3v_4\cdots v_{n-1}v_n v_1$.

Claim 1: Every edge $e$ on $C$ must receive the same color as one of its adjacent edges on $C$.

Proof. Assume this is not the case. Then there exist three consecutive edges on C that receive distinct colors. Assume without loss of generality that $\psi(v_1v_2) = 1, \; \psi(v_2v_3) = 2, \; \psi(v_3v_4) = 3,$ then the edge $u_2u_3$ cannot be colored.

Since $\psi$ is an injective edge coloring, no three consecutive edges can receive the same color. Therefore, the edges of $C$ can be divided into adjacent pairs and each pair receives the same color. In particular, $C$ must have even length.

Without loss of generality, we assume that $\; \psi(v_1v_2) = 1, \; \psi(v_2v_3) = 1, \; \psi(v_3v_4) = 2, \; \psi(v_4v_5) = 2$.

Claim 2: $\; \psi(v_5v_6) = \; \psi(v_6v_7) = 3$.

Proof. Clearly $\; \psi(v_5v_6) \neq 2$. Assume that $\; \psi(v_5v_6) = 1$. Then by Claim 1, $\; \psi(v_6v_7) = 1$. It follows that $\; \psi(u_5u_6) = 3$. Now the edge $u_3u_4$ can not be colored, a contradiction. Therefore, $\; \psi(v_5v_6) = 3$. By Claim 1, $\; \psi(v_6v_7) = 3$. This completes the proof of Claim 2.

By Claim 1 and 2, the edges of $C$ are colored in the pattern $112233\cdots$ (up to renaming colors). Therefore, the length of $C$ is a multiple of $6$.

On the other hand, if the length of $C$ is a multiple of $6$, then we give a $3$-injective edge coloring of $P(n, 1)$ in the following way. We first label some of the vertices in $P(n, 1)$ as follows: $L(v_i) = 1$ for $i\in \{1, 7, ..., n-5\}$; $L(v_i) = 2$ for $i\in \{3, 9, ..., n-3\}$; $L(v_i) = 3$ for $i\in \{5, 11, ..., n-1\}$; $L(u_i) = 1$ for $i\in \{4, 10, ..., n-2\}$; $L(u_i) = 2$ for $i\in \{6, 12, ..., n\}$; $L(u_i) = 3$ for $i\in \{2, 8, ..., n-4\}$. If a vertex $v$ is labelled, then we color the edges incident with $v$ by the color $L(v)$. Since $n$ is a multiple of $6$, all the edges are colored, and it is easy to check that this coloring is a $3$-injective edge coloring of $P(n, 1)$. Therefore, we complete the proof of this lemma.

Now we show that if $n > 6$ and $n$ is not a multiple of $6$, then there is a $4$-injective edge coloring of $P(n, 1)$.

Lemma 2.3. If $n\not\equiv0\; (mod\; 6)$ and $n > 6$, then $\chi_{i}^{'}(P(n, 1))\le 4.$

Proof. Clearly there are five cases depending on $n$ (modulo $6$). We will give the coloring in each case: we first label some of the vertices of $P(n, 1)$ with numbers in $\{1, 2, 3, 4\}$. Let $\phi$ be an edge coloring such that if a vertex $v$ is labelled by $L(v)$, then we color the edges incident with $v$ by the color $L(v)$. This edge coloring $\phi$ might not be injective edge coloring. If this is the case, then we adjust the colors of some edges to obtain an injective edge coloring $\psi$.

Case 1. $n = 6m+1, \; m\in N$. We label the vertices as follows:

● $L(v_i) = 1, \; L(u_j) = 1, \; i\in \{1, 7, 13, \ldots, n-6\}, \; j\in \{4, 10, 16, \ldots, n-3\};$

● $L(v_i) = 2, \; L(u_j) = 2, \; i\in \{5, 11, 17, \ldots, n-2\}, \; j\in \{2, 8, 14, \ldots, n-5\};$

● $L(v_i) = 3, \; L(u_j) = 3, \; i\in \{3, 9, 15, \ldots, n-4\}, \; j\in \{6, 12, 18, \ldots, n-1\}.$

Let $\phi$ be the edge coloring defined above. We can see that $\phi$ is not an injective edge coloring, so we adjust the colors of some edges in the following way:

Set $\psi (u_{n-2}u_{n-1}) = \psi (u_{n-1}v_{n-1}) = \psi (u_{n-1}u_{n}) = 4$, $\psi (u_{n}u_{1}) = \psi (u_{1}v_{1}) = \psi (u_{1}u_{2}) = 2$, $\psi(v_{n-1}v_n) = \psi(u_nv_n) = 3$, $\psi(v_2u_2) = \psi(u_2u_3) = 4$. Let $\psi(e) = \phi(e)$ for all the other edges of $P(n, 1)$. It is easy to check that the coloring $\psi$ is an injective edge coloring.

Case 2. $n = 6m+2, \; m\in N$. We label the vertices as follows:

● $L(v_i) = 1, \; L(u_j) = 1, \; i\in \{1, 7, 13, \ldots, n-7\}, \; j\in \{4, 10, 16, \ldots, n-4\};$

● $L(v_i) = 2, \; L(u_j) = 2, \; i\in \{5, 11, 17, \ldots, n-9\}, \; j\in \{2, 8, 14, \ldots, n-6\};$

● $L(v_i) = 3, \; L(u_j) = 3, \; i\in \{3, 9, 15, \ldots, n-5\}, \; j\in \{6, 12, 18, \ldots, n-8\}.$

Let $\phi$ be the coloring defined above. We define $\psi$ in the following way: $\psi(v_{n-4}v_{n-3}) = \psi(v_{n-3}v_{n-2}) = \psi(u_{n-3}v_{n-3}) = 4$, $\psi(u_{n-3}u_{n-2}) = \psi(u_{n-2}u_{n-1}) = \psi(u_{n-2}v_{n-2}) = 2$, $\psi(v_{n-2}v_{n-1}) = \psi(v_{n-1}v_{n}) = \psi(u_{n-1}v_{n-1}) = 3$, $\psi(u_{n-1}u_{n}) = \psi(u_{n}u_{1}) = \psi(u_{n}v_{n}) = 4,$ $\psi(e) = \phi(e)$ for all the other edges of $P(n, 1)$. It is easy to check that $\psi$ is an injective edge coloring of $P(n, 1)$.

Case 3. $n = 6m+3, \; m\in N$. We label the vertices as follows:

● $L(v_i) = 1, L(u_j) = 1, i\in \{1, 7, 13, \ldots, n-8\}, j\in \{4, 10, 16, \ldots, n-5\};$

● $L(v_i) = 2, L(u_j) = 2, i\in \{5, 11, 17, \ldots, n-4\}, j\in \{2, 8, 14, \ldots, n-7\};$

● $L(v_i) = 3, L(u_j) = 3, i\in \{3, 9, 15, \ldots, n-6\}, j\in \{6, 12, 18, \ldots, n-3\}.$

Let $\phi$ be the coloring defined above. We define $\psi$ in the following way: $\psi(v_{n-3}v_{n-2}) = \psi(u_{n-2}v_{n-2}) = 1$, $\psi(u_{n-2}u_{n-1}) = \psi(u_{n-1}u_n) = 2,$ $\psi(u_nv_n) = \psi(u_nu_1) = 3$, $\psi(v_{n-2}v_{n-1}) = \psi(v_{n-1}u_{n-1}) = \psi(v_{n-1}v_n) = 4,$ $\psi(u_{1}u_2) = 4$, $\psi(e) = \phi(e)$ for all the other edges of $P(n, 1)$. It is easy to check that $\psi$ is an injective edge coloring of $P(n, 1)$.

Case 4. $n = 6m+4, \; m\in N$. We label the vertices as follows:

● $L(v_i) = 1, L(u_j) = 1, i\in \{1, 7, 13, \ldots, n-3\}, j\in \{4, 10, 16, \ldots, n-6\};$

● $L(v_i) = 2, L(u_j) = 2, i\in \{5, 11, 17, \ldots, n-5\}, j\in \{2, 8, 14, \ldots, n-2\};$

● $L(v_i) = 3, L(u_j) = 3, i\in \{3, 9, 15, \ldots, n-1\}, j\in \{6, 12, 18, \ldots, n-4\}.$

Let $\phi$ be the coloring defined above. We define $\psi$ as follows: $\psi(u_{n-1}u_{n}) = \psi(u_{n}v_{n}) = \psi(u_{n}u_1) = 4,$ $\psi(e) = \phi(e)$ for all the other edges of $P(n, 1)$. Then $\psi$ is an injective edge coloring of $P(n, 1)$.

Case 5. $n = 6m+5, \; m\in N$. We label the vertices as follows:

● $L(v_i) = 1, L(u_j) = 1, i\in \{1, 7, 13, \ldots, n-10\}, j\in \{4, 10, 16, \ldots, n-7\};$

● $L(v_i) = 2, L(u_j) = 2, i\in \{5, 11, 17, \ldots, n-6\}, j\in \{2, 8, 14, \ldots, n-9\};$

● $L(v_i) = 3, L(u_j) = 3, i\in \{3, 9, 15, \ldots, n-8\}, j\in \{6, 12, 18, \ldots, n-5\};$

● $L(v_{n-4}) = L(u_n) = 4,$ $L(u_{n-2}) = 1.$

Let $\phi$ be the coloring defined above. We define $\psi$ in the following way: $\psi(u_{n-4}u_{n-3}) = \psi(u_{n-3}v_{n-3}) = 2, \; \psi(v_{n-3}v_{n-2}) = \psi(v_{n-2}v_{n-1}) = 3, \; \psi(v_{n-1}v_n) = \psi(v_{n-1}u_{n-1}) = 2,$ $\psi(e) = \phi(e)$ for all the other edges of $P(n, 1)$. Then $\psi$ is an injective edge coloring of $P(n, 1)$.

It follows from Cases 1-5 that $\chi_{i}^{'}(P(n, 1))\leq 4$ for all $n$ with $n\not\equiv0\; (mod\; 6)$ and $n > 6$.

Next we determine $\chi_{i}^{'}(P(n, 1))$ for $3 \leq n\leq 5$.

Lemma 2.4. $\chi_{i}^{'}(P(3, 1)) = 6$.

Proof. Since every pair of edges in $\{ u_1u_2, \; u_2u_3, \; u_3u_1, v_1v_2, \; v_2v_3, \; v_3v_1 \}$ see each other, they should be colored with different colors. This implies that $\chi_{i}^{'}(P(3, 1))\ge 6$. On the other hand, $P(3, 1)$ has a $6$-injective edge coloring as follows: $\psi(u_1v_1) = \psi(u_1u_2) = 1$; $\psi(u_2v_2) = \psi(u_2u_3) = 2$; $\psi(u_3v_3) = \psi(u_3u_1) = 3$; $\psi(v_1v_2) = 4;\; \psi(v_2v_3) = 5;\psi(v_3v_1) = 6\;$. Therefore, $\chi_{i}^{'}(P(3, 1)) = 6$.

Lemma 2.5. $\chi_{i}^{'}(P(4, 1)) = 4$.

Proof. Since every pair of edges in $\{ v_1v_2, u_2u_3, v_3v_4, u_4u_1\}$ see each other, they must be colored with different colors. So $\chi_{i}^{'}(P(4, 1))\ge 4$. On the other hand, $P(4, 1)$ has a $4$-injective edge coloring as follows: $\psi(u_1v_1) = \psi(u_1u_2) = \psi(u_1u_4) = 1$; $\psi(v_2u_2) = \psi(v_2v_1) = \psi(v_2v_3) = 2$; $\psi(u_3u_2) = \psi(u_3v_3) = \psi(u_3u_4) = 3$; $\psi(v_4u_4) = \psi(v_4v_3) = \psi(v_4v_1) = 4$. Therefore, $\chi_{i}^{'}(P(4, 1)) = 4$.

Lemma 2.6. $\chi_{i}^{'}(P(5, 1)) = 5$.

Proof. By Lemma 2.1, we have that $\chi_{i}^{'}(P(5, 1))\ge 3$. We claim that $\chi_{i}^{'}(P(5, 1))\ge 4$, for otherwise we would color the outer cycle with three colors. Then there exist three consecutive edges on the outer cycle that are colored differently. Without loss of generality, let $\psi(u_1u_2) = 1, \; \psi(u_2u_3) = 2, \; \psi(u_3u_4) = 3$, then the edge $v_2v_3$ must be colored with a fourth color, and hence, $\chi_{i}^{'}(P(5, 1))\ge 4$.

Next we show that $\chi_{i}^{'}(P(5, 1))\ge 5$. We assume by contradiction that $P(n, 1)$ has an injective edge coloring using four colors.

If only three colors are used to color the edges of the outer cycle, then there are two pairs of adjacent edges such that each pair is colored with one color and the remaining edge is colored with a third color. Without loss of generality, let $\psi(u_1u_2) = \psi(u_2u_3) = 1, \; \psi(u_3u_4) = 2, \; \psi(u_4u_5) = 2, \; \psi(u_5u_1) = 3$, then we must have that $\psi(v_5v_1) = 4, \; \psi(v_2v_3) = 3, \; \psi(v_3v_4) = 3, \; \psi(u_1v_1) = 4$, but now the edge $u_5v_5$ cannot be colored.

If four colors are used to color the edges of the outer cycle, then there are two adjacent edges colored with the same color, all other edges are colored differently. Without loss of generality, let $\psi(u_1u_2) = 1, \; \psi(u_2u_3) = 1, \; \psi(u_3u_4) = 2, \; \psi(u_4u_5) = 3, \; \psi(u_5u_1) = 4$, then we get that $\psi(v_5v_1) = 2, \; {\psi(v_3v_4) = 4}, \; \psi(u_4v_4) = 3$, but now the edge $u_5v_5$ cannot be colored.

So an injective edge coloring of $P(5, 1)$ requires at least five colors, that is, $\chi_{i}^{'}(P(5, 1))\ge5$. In Figure 7, we give a 5-injective edge coloring of $P(5, 1)$, therefore, $\chi_{i}^{'}(P(5, 1)) = 5$.

Combining Lemma 2.1 to Lemma 2.6, we obtain the exact values of injective edge coloring numbers of $P(n, 1)$ for $n\geq 3,$ which completes the proof of Theorem 1.1.

3.   Injective edge coloring of $P(n, 2)$

In this section, we study the injective edge coloring number of $P(n, 2)$. We first show that $\chi_{i}^{'}(P(n, 2))\geq 4$.

Lemma 3.1. If $n\geq6$, then $\chi_{i}^{'}(P(n, 2))\geq 4$.

Proof. Suppose by contradiction that $\chi_{i}^{'}(P(n, 2)) = 3$. Let $\psi$ be a $3$-injective edge coloring of $P(n, 2)$. We may assume that $\psi(u_iv_i) = 1$. Then since every pair of edges in $\{ u_iv_i, \; u_{i-1}v_{i-1}, \; u_{i+1}v_{i+1} \}$ see each other, they must be colored differently. Without loss of generality, let $\psi(u_{i-1}v_{i-1}) = 2, \; \psi(u_{i+1}v_{i+1}) = 3.$ Then we have $\psi(u_{i+2}v_{i+2}) = 2, \; \psi(u_{i+3}v_{i+3}) = 1, \; \psi(u_{i+4}v_{i+4}) = 3.$ Now note that $\psi(u_{i+1}u_{i+2}) = 2$ or $3$.

Case 1. $\psi(u_{i+1}u_{i+2}) = 2$: Since the edge $v_iv_{i+2}$ sees the edges $u_{i+1}u_{i+2}$ and $u_{i+4}v_{i+4}$, $\psi(v_iv_{i+2}) = 1$. Similarly, $\psi(u_iu_{i+1}) = 3$. But then since the edge $v_{i-1}v_{i+1}$ sees edges $u_iu_{i+1}, u_{i+1}u_{i+2}, u_{i+3}v_{i+3}$, it must be colored with a fourth color, a contradiction.

Case 2. $\psi(u_{i+1}u_{i+2}) = 3$: Since the edge $v_{i+2}v_{i+4}$ sees the edges $u_{i+1}u_{i+2}$ and $u_{i}v_{i}$, $v_{i+2}v_{i+4}$ must be colored with 2. Similarly, $\psi(u_{i+2}u_{i+3}) = 1$. Now since the edge $v_{i+1}v_{i+3}$ sees edges $u_{i-1}v_{i-1}, u_{i+1}u_{i+2}, u_{i+2}u_{i+3}$, it must be colored with a fourth color, a contradiction.

Therefore, at least four colors are required in an injective edge coloring of $P(n, 2)$.

Next we find a $5$-injective edge coloring of $P(n, 2)$ where $n \geq 8$. There are two cases depending on whether $n$ is even or odd.

Lemma 3.2. If $n\geq 8$ and $n$ is even, then $\chi_{i}^{'}(P(n, 2))\leq5$.

Proof. Let $n = 2q$. The inner vertices of $P(n, 2)$ induce two cycles, each of length $q$. We denote these two cycles as $C_1$ and $C_2$, where $C_1 = v_1v_3\ldots v_{2q-1}v_1$ and $C_2 = v_2v_4\ldots v_{2q}v_2$. The graph $P(2q, 2)$ is shown in Figure 9.

Case 1. $2q = 4m+2,$ $m\geq 2$ and $m\in N$.

We first label some of the vertices on the outer cycle as follows: $L(u_i) = 1$ for $i\in \{1, 5, 9, \ldots, 2q-5\}$, $L(u_i) = 2$ for $i\in \{3, 7, 11, \ldots, 2q-3\}$, $L(u_{2q-1}) = 3.$ Then if a vertex is labelled, we color the three edges incident with this vertex by its labelling. Now the uncolored edges are the edges on the cycles $C_1$ and $C_2$, and the edges $u_{2i}v_{2i}$ for $1\leq i\leq q$.

Subcase 1.1. $q\equiv1\; (mod\; 4)$. For the edges on the cycle $C_1$, let $\psi(v_3v_5) = 3$, the other edges $v_5v_7, v_7v_9, \ldots, v_1v_3$ are colored in the order 44554455$\ldots$ 55. For the edges on the cycle $C_2$, let $\psi(v_2v_4) = \psi(v_4v_6) = 3,$ the other edges $v_6v_8, v_8v_{10}, \ldots, v_{2q}v_2$ are colored in the order 44554455$\ldots$ 5. Finally, let $\psi(u_{2i}v_{2i}) = 3$ for $i\in \{5, 7, 9, \ldots, q-2\}$, $\psi(u_{2i}v_{2i}) = 4$ for $i\in \{4, 8, \ldots, q-1\},$ $\psi(u_{2i}v_{2i}) = 5$ for $i\in \{6, 10, \ldots, q-3\},$ $\psi(u_2v_2) = \psi(u_6v_6) = 5,$ $\psi(u_{4}v_4) = 3$, $\psi(u_{2q}v_{2q}) = 2$. It's easy to check that the coloring $\psi$ is an injective edge coloring of $P(2q, 2)$.

Subcase 1.2. $q\equiv3\; (mod\; 4)$. Then $q-2\equiv1\; (mod\; 4)$. For the edges on the cycle $C_1$, let $\psi(v_3v_5) = \psi(v_5v_7) = 3,$ the other edges $v_7v_9, v_9v_{11}, \ldots, v_1v_3$ are colored in the order 44554455$\ldots$ 554. For the edges on the cycle $C_2$, let $\psi(v_2v_4) = \psi(v_4v_6) = 3$, the other edges $v_6v_8, v_8v_{10}, \ldots, v_{2q}v_2$ are colored in the order 44554455$\ldots$ 554. Finally, let $\psi(u_{2i}v_{2i}) = 3$ for $i\in \{5, 7, 9, \ldots, q-2\}$, $\psi(u_{2i}v_{2i}) = 4$ for $i\in \{4, 8, \ldots, q-3\},$ $\psi(u_{2i}v_{2i}) = 5$ for $i\in \{6, 10, \ldots, q-1\},$ $\psi(u_2v_2) = 4,$ $\psi(u_{4}v_4) = 3$, $\psi(u_6v_6) = 5$, $\psi(u_{2q}v_{2q}) = 2$. It's easy to check that the coloring $\psi$ is an injective edge coloring of $P(2q, 2)$.

Case 2. $2q = 4m,$ $m\geq 2$ and $m\in N$.

In this case, the labelling of the vertices on the outer cycle are: $L(u_i) = 1$ for $i\in \{1, 5, 9, 13, \ldots, 2q-3\}$, $L(u_i) = 2$ for $i\in \{3, 7, 11, 15, \ldots, 2q-1\}$. Similar to Case 1, if a vertex is labelled, we color the three edges incident with this vertex by its labelling. Now the uncolored edges are the edges on the cycles $C_1$ and $C_2$, and the edges $u_{2i}v_{2i}$ for $1\leq i\leq q$.

Subcase 2.1. $q\equiv2\; (mod\; 4).$ For the edges on the cycle $C_1$, let $\psi(v_1v_3) = \psi(v_3v_5) = 3$, the other edges $v_5v_7, v_7v_9, \ldots, v_{2q-1}v_1$ are colored in the order 44554455$\ldots$ 55. For the edges on the cycle $C_2$, let $\psi(v_2v_4) = \psi(v_4v_6) = 3,$ the other edges $v_6v_8, v_8v_{10}, \ldots, v_{2q}v_2$ are colored in the order 44554455$\ldots$ 55. Finally, let $\psi(u_{2i}v_{2i}) = 3$ for $i\in \{5, 7, 9, \ldots, q-1\}$, $\psi(u_{2i}v_{2i}) = 4$ for $i\in \{4, 8, \ldots, q-2\},$ $\psi(u_{2i}v_{2i}) = 5$ for $i\in \{6, 10, \ldots, q\},$ $\psi(u_2v_2) = 4,$ $\psi(u_{4}v_4) = 3$, $\psi(u_6v_6) = 5$. It's easy to check that the coloring $\psi$ is an injective edge coloring of $P(2q, 2)$.

Subcase 2.2. $q\equiv0\; (mod\; 4).$ We color the edges $v_1v_3, v_3v_5, \ldots, v_{2q-1}v_1$ on the cycle $C_1$ and the edges $v_2v_4, v_4v_6, \ldots, v_{2q}v_2$ on the cycle $C_2$ both in the order 33443344$\cdots$ 44. Then let $\psi(u_{2i}v_{2i}) = 3$ for $i\in \{2, 6, \ldots, q-2\}$, $\psi(u_{2i}v_{2i}) = 4$ for $i\in \{4, 8, \ldots, q\},$ $\psi(u_{2i}v_{2i}) = 5$ for $i\in \{1, 3, 5, \ldots, q-1\}.$ It's easy to check that the coloring $\psi$ is an injective edge coloring of $P(2q, 2)$.

Lemma 3.3. If $n\geq 9$ and $n$ is odd, then $\chi_{i}^{'}(P(n, 2))\leq5$.

Proof. Since $n$ is odd, the inner vertices of $P(n, 2)$ induce a cycle of length $n$, denote the cycle as $C$, where $C = v_1v_3v_5\cdots v_{n-2}v_nv_2v_4\cdots v_{n-1}v_1$. It suffices to consider the following five cases.

Case 1. $n = 5m,$ $m\geq 2$:

Since $n$ is odd, $m$ is odd. We color the edges as follows:

● $\psi(u_iv_i) = 1$ for $i\in \{1, 6, 11, \ldots, n-4\};$ $\psi(u_iv_i) = 2$ for $i\in \{2, 7, 12, \ldots, n-3\};$ $\psi(u_iv_i) = 3$ for $i\in \{3, 8, 13, \ldots, n-2\};$ $\psi(u_iv_i) = 4$ for $i\in \{4, 9, 14, \ldots, n-1\};$ $\psi(u_iv_i) = 5$ for $i\in \{5, 10, 15, \ldots, n\}.$

● $\psi(u_{i-1}u_i) = \psi(u_iu_{i+1}) = \psi(u_iv_i)$ for $i\in \{3, 5, 7, 9, \ldots, n-2\};$ $\psi(u_{n-1}u_n) = 2, \psi(u_nu_1) = \psi(u_1u_2) = 1.$

● $\psi(v_iv_{i+2}) = \psi(u_{i+1}v_{i+1})$ for $i\in \{1, 3, 5, \ldots, n-2\};$ $\psi(v_iv_{i+2}) = \psi(u_{i+2}v_{i+2})$ for $i\in \{2, 4, 6, \ldots, n-3\};$ $\psi(v_{n-1}v_1) = 5, \psi(v_nv_2) = 5.$

Now we obtain a 5-injective edge coloring of $P(n, 2)$.

Case 2. If $n = 5m+1,$ $m\geq 2$:

In this case $m$ must be even since $n$ is odd. Let

● $\psi(u_iv_i) = 1$ for $i\in \{1, 6, 11, \ldots, n-5\};$ $\psi(u_iv_i) = 2$ for $i\in \{2, 7, 12, \ldots, n-4\};$ $\psi(u_iv_i) = 3$ for $i\in \{3, 8, 13, \ldots, n-3\};$ $\psi(u_iv_i) = 4$ for $i\in \{4, 9, 14, \ldots, n-2\};$ $\psi(u_iv_i) = 5$ for $i\in \{5, 10, 15, \ldots, n-1\};$ $\psi(u_nv_n) = 3.$

● $\psi(u_{i-1}u_i) = \psi(u_iu_{i+1}) = \psi(u_iv_i)$ for $i\in \{3, 5, 7, \ldots, n-2\};$ $\psi(u_{n-1}u_n) = 3, \psi(u_nu_1) = \psi(u_1u_2) = 1.$

● $\psi(v_iv_{i+2}) = \psi(u_{i+1}v_{i+1})$ for $i\in \{1, 3, 5, \ldots, n-6\};$ $\psi(v_iv_{i+2}) = \psi(u_{i+2}v_{i+2})$ for $i\in \{2, 4, 6, \cdots, n-3\};$ $\psi(v_{n-4}v_{n-2}) = 1, \; \psi(v_{n-2}v_n) = 5, \; \psi(v_nv_2) = 2, \; \psi(v_{n-1}v_1) = 2.$

This way we obtain a 5-injective edge coloring of $P(n, 2)$.

Case 3. If $n = 5m+2,$ $m\geq 2$:

In this case $m$ is odd. Let

● $\psi(u_iv_i) = 1$ for $i\in \{1, 6, 11, \ldots, n-6\};$ $\psi(u_iv_i) = 2$ for $i\in \{2, 7, 12, \ldots, n-5\};$ $\psi(u_iv_i) = 3$ for $i\in \{3, 8, 13, \ldots, n-4\};$ $\psi(u_iv_i) = 4$ for $i\in \{4, 9, 14, \ldots, n-3\};$ $\psi(u_iv_i) = 5$ for $i\in \{5, 10, 15, \ldots, n-7\};$ $\psi(u_{n-2}v_{n-2}) = 2, \; \psi(u_{n-1}v_{n-1}) = 5, \; \psi(u_nv_n) = 3.$

● $\psi(u_{i-1}u_i) = \psi(u_iu_{i+1}) = \psi(u_iv_i)$ for $i\in \{3, 5, 7, \ldots, n-2\};$ $\psi(u_{n-1}u_n) = 3, \; \psi(u_nu_1) = \psi(u_1u_2) = 1.$

● $\psi(v_iv_{i+2}) = \psi(u_{i+1}v_{i+1})$ for $i\in \{1, 3, 5, \ldots, n-8\};$ $\psi(v_iv_{i+2}) = \psi(u_{i+2}v_{i+2})$ for $i\in \{4, 6, 8, \ldots, n-7\};$ $\psi(v_{n-6}v_{n-4}) = 5, \; \psi(v_{n-4}v_{n-2}) = 4, \; \psi(v_{n-2}v_n) = 4, \; \psi(v_nv_2) = 5, \; \psi(v_2v_4) = 2; \psi(v_{n-5}v_{n-3}) = 4, \; \psi(v_{n-3}v_{n-1}) = 4, \; \psi(v_{n-1}v_1) = 5.$

It is easy to check that this way we obtain a 5-injective edge coloring of $P(n, 2)$.

Case 4. If $n = 5m+3,$ $m\geq 2$:

Then $m$ is even. Let

● $\psi(u_iv_i) = 1$ for $i\in \{1, 6, 11, \ldots, n-2\};$ $\psi(u_iv_i) = 2$ for $i\in \{2, 7, 12, \ldots, n-1\};$ $\psi(u_iv_i) = 3$ for $i\in \{3, 8, 13, \ldots, n-5\};$ $\psi(u_iv_i) = 4$ for $i\in \{4, 9, 14, \ldots, n-4\};$ $\psi(u_iv_i) = 5$ for $i\in \{5, 10, 15, \ldots, n-3\};$ $\psi(u_nv_n) = 4.$

● $\psi(u_{i-1}u_i) = \psi(u_iu_{i+1}) = \psi(u_iv_i)$ for $i\in \{3, 5, 7, \ldots, n-4\};$ $\psi(u_{n-3}u_{n-2}) = 1, \psi(u_{n-2}u_{n-1}) = 3, \psi(u_{n-1}u_n) = 3, \psi(u_nu_1) = 1, \psi(u_1u_2) = 1$.

● $\psi(v_iv_{i+2}) = \psi(u_{i+1}v_{i+1})$ for $i\in \{3, 5, 7, \ldots, n-4\};$ $\psi(v_iv_{i+2}) = \psi(u_{i+2}v_{i+2})$ for $i\in \{4, 6, 8, \ldots, n-5\};$ $\psi(v_{n-3}v_{n-1}) = 2, \psi(v_{n-1}v_1) = 2, \psi(v_1v_3) = 4, \psi(v_{n-2}v_n) = 5, \psi(v_nv_2) = 2, \psi(v_2v_4) = 2.$

We again obtain a $5$-injective edge coloring of $P(n, 2)$.

Case 5. If $n = 5m+4,$ $m\geq 2$:

Then $m$ is odd since $n$ is odd. Let

● $\psi(u_iv_i) = 1$ for $i\in \{1, 6, 11, \ldots, n-3\};$ $\psi(u_iv_i) = 2$ for $i\in \{2, 7, 12, \ldots, n-2\};$ $\psi(u_iv_i) = 3$ for $i\in \{3, 8, 13, \ldots, n-1\};$ $\psi(u_iv_i) = 4$ for $i\in \{4, 9, 14, \ldots, n\};$ $\psi(u_iv_i) = 5$ for $i\in \{5, 10, 15, \ldots, n-4\}.$

● $\psi(u_{i-1}u_i) = \psi(u_iu_{i+1}) = \psi(u_iv_i)$ for $i\in \{3, 5, 7, \ldots, n-2\};$ $\psi(u_{n-1}u_n) = 4, \; \psi(u_nu_1) = \psi(u_1u_2) = 1.$

● $\psi(v_iv_{i+2}) = \psi(u_{i+1}v_{i+1})$ for $i\in \{1, 3, 5, \ldots, n-2\};$ $\psi(v_iv_{i+2}) = \psi(u_{i+2}v_{i+2})$ for $i\in \{2, 4, 6, \ldots, n-3\};$ $\psi(v_{n-1}v_1) = 5, \psi(v_nv_2) = 5, \psi(v_2v_4) = 2.$

We again obtain a 5-injective edge coloring of $P(n, 2)$.

It follows from Lemma 3.2 and Lemma 3.3 that $\chi_{i}^{'}(P(n, 2))\leq 5$ for $n\geq 8$.

Now we study $\chi_{i}^{'}(P(n, 2))$ for $4\leq n\leq 7$. If $n = 5$, then the graph $P(5, 2)$ is just the Petersen graph, by proposition 1, $\chi_{i}^{'}(P(5, 2)) = 5.$

Lemma 3.4. $\chi_{i}^{'}(P(4, 2)) = 4.$

Proof. Since every pair of edges in $\{u_1v_1, \; u_2v_2, \; u_3v_3, \; u_4v_4\}$ see each other, they should be colored differently, that is, $\chi_{i}^{'}(P(4, 2))\ge4$. On the other hand, $P(4, 2)$ has a $4$-injective edge coloring as follows: $\psi(u_1v_1) = \psi(u_1u_2) = \psi(u_1u_4) = 1$; $\psi(u_3u_2) = \psi(u_3v_3) = \psi(u_3u_4) = 2$; $\psi(u_2v_2) = \psi(v_1v_3) = 3$; $\psi(v_4u_4) = \psi(v_2v_4) = 4$. Therefore, $\chi_{i}^{'}(P(4, 2)) = 4$.

Lemma 3.5. $\chi_{i}^{'}(P(6, 2)) = 5.$

Proof. Denote the outer cycle of $P(6, 2)$ as $C = u_1u_2u_3u_4u_5u_6u_1$. By Lemma 3.1, $\chi_{i}^{'}(P(6, 2))\ge4$. Assume by contradiction that $P(6, 2)$ has a 4-injective edge coloring.

Case 1. Only three colors are used to color the edges of $C$.

In any $3$-injective edge coloring of $C$, there exist two adjacent edges that are colored differently, and each color is used twice. Without loss of generality, let $\psi(u_1u_2) = 1, \psi(u_2u_3) = 2$. By symmetry, we only need to consider the cases $\psi(u_3u_4) = 3$ or $\psi(u_4u_5) = 3$.

If $\psi(u_3u_4) = 3$, then $\psi(v_2v_4) = 4$. Since the edge $v_4v_6$ sees edges $u_4u_5, \; u_5u_6,$ $u_6u_1, \; v_2v_4$, these four edges are colored with different colors in $\{1, 2, 3, 4\}$. So $v_4v_6$ cannot be colored.

If $\psi(u_4u_5) = 3$, then $\psi(v_2v_4) = 4$. Similarly, the edge $v_4v_6$ cannot be colored.

Case 2. Four colors are used to color the edges of $C$.

First note that there exist no four successive edges $u_iu_{i+1}, \; u_{i+1}u_{i+2}, \; u_{i+2}u_{i+3},$ $u_{i+3}u_{i+4}$ that are colored differently, because otherwise the edge $v_{i+1}v_{i+3}$ cannot be colored. So there exists an $i$ such that $\psi(u_iu_{i+1}) = \psi(u_{i+1}u_{i+2})$, $\psi(u_{i+3}u_{i+4}) = \psi(u_{i+4}u_{i+5})$, the subscripts are taken modulo 6. Without loss of generality, let $\psi(u_1u_2) = \psi(u_2u_3) = 1,$ $\psi(u_3u_4) = 2,$ $\psi(u_4u_5) = \psi(u_5u_6) = 3,$ and $\psi(u_6u_1) = 4$. Then we have that $\psi(v_2v_4) = 4, \psi(u_6v_6) = 2, \psi(v_3v_5) = 4,$ and hence, the edge $u_1v_1$ cannot be colored.

Therefore, at least five colors are needed in an injective edge coloring of $P(6, 2),$ that is $\chi_{i}^{'}(P(6, 2))\ge 5.$ On the other hand, Figure 19 shows a 5-injective edge coloring of $P(6, 2)$. So we have that $\chi_{i}^{'}(P(6, 2)) = 5$, as required.

Lemma 3.6. $\chi_{i}^{'}(P(7, 2)) = 5.$

Proof. Denote the outer cycle of $P(7, 2)$ by $C = u_1u_2u_3u_4u_5u_6u_7u_1$. By Lemma 3.1, $\chi_{i}^{'}(P(7, 2))\ge4$. We assume by contradiction that $P(7, 2)$ has a $4$-injective edge coloring.

Case 1. Only three colors are used to color the edges of $C$:

Then there exist three edges colored with the same color, two of them must be adjacent, and the third one is opposite to them. Without loss of generality, let $\psi(u_1u_2) = \psi(u_2u_3) = \psi(u_5u_6) = 1$. By symmetry, if suffices to consider the following three sub-cases.

If $\psi(u_1u_2) = 1, \; \psi(u_2u_3) = 1, \; \psi(u_3u_4) = 2, \; \psi(u_4u_5) = 2, \; \psi(u_5u_6) = 1, \; \psi(u_6u_7) = 3, \; \psi(u_7u_1) = 2,$ then the edge $v_7v_2$ must be colored with 4, but now the edge $v_4v_6$ cannot be colored.

If $\psi(u_1u_2) = 1, \; \psi(u_2u_3) = 1, \; \psi(u_3u_4) = 2, \; \psi(u_4u_5) = 2, \; \psi(u_5u_6) = 1, \; \psi(u_6u_7) = 3, \; \psi(u_7u_1) = 3,$ then the edge $v_4v_6$ must be colored with 4, but now the edge $v_1v_3$ cannot be colored.

If $\psi(u_1u_2) = 1, \; \psi(u_2u_3) = 1, \; \psi(u_3u_4) = 2, \; \psi(u_4u_5) = 3, \; \psi(u_5u_6) = 1, \; \psi(u_6u_7) = 2, \; \psi(u_7u_1) = 3,$ then the edge $v_7v_2$ must be colored with 4, but now the edge $v_3v_5$ cannot be colored.

Case 2. Four colors are used to color the edges of $C$:

First note that there exist no four successive edges $u_iu_{i+1}, \; u_{i+1}u_{i+2}, \; u_{i+2}u_{i+3},$ $u_{i+3}u_{i+4}$ (the subscripts are taken modulo $7$) that are colored differently, because otherwise the edge $v_{i+1}v_{i+3}$ cannot be colored. Since there are four colors and seven edges on $C$, at least one color, say 4, that is used only once. Without loss of generality, let $\psi(u_1u_2) = 4$. Since edges $u_2u_3, \; u_7u_1, \; u_1u_2$ are colored differently, suppose $\psi(u_2u_3) = 1$ and $\psi(u_7u_1) = 2$, then $u_3u_4$ and $u_6u_7$ must be colored with 1 or 2. So $\psi(u_4u_5) = 3$ or $\psi(u_5u_6) = 3$.

In both case, we have that $\psi(u_3u_4) = 1$, $\psi(u_4u_5) = 3$, $\psi(u_5u_6) = 3$ and $\psi(u_6u_7) = 2$. Then we deduce that $\psi(v_2v_4) = 2, \; \psi(v_4v_6) = 4, \; \psi(u_7v_7) = 1, \; \psi(u_1v_1) = 3$, now the edge $u_2v_2$ cannot be colored, a contradiction.

So we have shown that $\chi_{i}^{'}(P(7, 2))\ge 5.$ In Figure 20, we give a $5$-injective edge coloring of $P(7, 2)$. Therefore, $\chi_{i}^{'}(P(7, 2)) = 5$.

From Lemma 3.1 to Lemma 3.6, we complete the proof of Theorem1.2.

4.   Conclusions

In this paper, we have determined the exact values of the injective edge coloring numbers for $P(n, 1)$ with $n\geq 3$ and for $P(n, 2)$ with $4\leq n\leq 7$. For $n\geq 8$, we have showed that $4\leq \chi_{i}^{'}(P(n, 2))\leq 5.$ However, we don't know whether the exact values of the injective edge coloring numbers for $P(n, 2)$ are $4$ or $5$. We conjecture that $\chi_{i}^{'}(P(n, 2)) = 5.$ It is also open to compute the exact values of the injective edge coloring numbers of $P(n, k)$ for $k\geq 3$.

Acknowledgments

This work is supported by the Natural Science Foundation of Fujian Province (No. 2020J05058).

Conflict of interest

The authors declare no conflict of interest.