Path Decomposition Number of Certain Graphs

1. Introduction

Let \(P_m\), \(C_m\), \(K_m\), \(K_m-I\), \(K_{m,m}-I\) denote path of length \(m\), cycle of length \(m\), complete graph on \(m\) vertices, complete graph on \(m\) vertices minus a 1-factor and complete bipartite graph on \(2m\) vertices minus a 1-factor respectively. All graphs considered in this paper are simple, finite and connected. We refer to the book [1] for graph theoretic terminology used in this article. A graph is said to be it decomposed into subgraphs \(H_1\) and \(H_2\) which is denoted by \(G= H_1 \oplus H_2\), if \(G\) is the edge disjoint union of \(H_1\) and \(H_2\). Assume that \(G= H_1 \oplus H_2 \oplus \cdots \oplus H_k\) and if each \(H_i\), \(1 \leq i \leq k\), is a path or cycle in \(G\), then the collection of edge-disjoint subgraphs of \(G\) denoted by \(\psi\) is called a path decomposition of \(G\). If each \(H_i\) is a path in \(G\) then \(\psi\) is called an acyclic path decomposition of \(G\). The minimum cardinality of a path decomposition of \(G\), denoted by \(\pi(G)\), is called the path decomposition number and the minimum cardinality of an acyclic path decomposition of \(G\), denoted by \(\pi_a(G)\), is called the acyclic path decomposition number of \(G\). If \(P=(x_1,x_2,...,x_m)\) is a path in a graph \(G\), then the vertices \(x_2,x_3,...,x_{m-1}\) are called the internal vertices of \(P\) and \(x_1\), \(x_m\) are called external vertices of \(P\). Here, by a first vertex and end vertex of path \(P\) we mean the vertices \(x_1\) and \(x_m\) respectively. Let \(P=(x_1,x_2,...,x_m)\) and \(Q=(y_1,y_2,...,y_m)\) be two paths in \(G\), by joining \(x_1\) to \(y_1\) (\(x_m\) to \(y_m\), respectively) we obtain the path \(R=(y_m,y_{m-1},...,y_1,x_1,x_2,...,x_m)\) \(\big (R=(x_1,x_2,...,x_m,y_m,y_{m-1},...,y_1)\), respectively \(\big )\).

Definition 1.1. The Cartesian product \(G \ \Box \ H\) of two graphs \(G\) and \(H\) is a graph with vertex set \(V(G)\times V(H)\) in which \((x_1,y_1)\) and \((x_2,y_2)\) are adjacent if one of the following condition holds:

• \(x_1= x_2\) and \(\{y_1,y_2\}\in E(H)\).
• \(y_1= y_2\) and \(\{x_1,x_2\}\in E(G)\).

The graphs \(G\) and \(H\) are known as the factors of \(G \ \Box \ H\).

Suppose we are dealing with \(m\)-copies of a graph \(G\) we denote these \(m\)-copies of \(G\) by \(G^i\), where \((i=1,2,3,...,m)\).
The Cartesian product graph \(G \ \Box \ H\) may also be viewed as the graph obtained from \(G\) by replacing each vertex \(i \in V(G)\) by a copy \(H^i\) (say) of \(H\) and each of its edges \(\{i, k\}\) with \(|V (H)|\) edges joining corresponding vertices of \(H^i\) and \(H^k\).
Henceforth, for any vertex \(i \in V(G)\) we refer the copy of \(H\), denoted by \(H^i\), in \(G \ \Box \ H\) corresponding to the vertex \(i\) as the \(i^{th}\) copy of \(H\) in \(G \ \Box \ H\).
The problem of finding \(C_k\)-decomposition of \(K_{2n+1}\) or \(K_{2n}-I\) where \(I\) is a 1-factor of \(K_{2n}\), is completely settled by Alspach, Gavlas and Sajna in two different papers (see [2, 3]). Obviously, every graph admits a decomposition in which each subgraph \(H_i\) is either a path or a cycle. Gallai conjectured that the minimum number of paths into which every connected graph on \(n\) vertices can be decomposed into is not less than \(\lceil \frac{n}{2} \rceil\) (see [4]). A significant contribution to the parameter \(\pi\) was by Lovasz [4] when he proved that a graph on \(n\) vertices can be decomposed into \(\lfloor \frac{n}{2} \rfloor\) paths and cycles. Harary introduced the parameter \(\pi_a\), this was further studied by Harary and Schwenk in [5] when they considered the evolution number of the path number of a given graph. Staton it et al. in [6, 7] provided further results on path numbers and considered the case of the tripartite graphs. P\'eroche [8] gave some results on the path numbers of certain multipartite graphs. Arumugam and Suseela [9] shed some lights on the acyclic path decomposition of unicyclic graphs. A recent work by Arumugam it et al. [10] studied the parameter \(\pi\) and further determined the value of \(\pi\) for some graphs. They also provided some bounds for \(\pi\) and characterize graphs attaining the bounds. Furthermore, they proved that the difference between the parameter \(\pi\) and \(\pi_a\) can be arbitrary large.
In this paper, we determine the value of \(\pi\) for the graph \(K_n-I\), \(K_{n,n}-I\) and the Cartesian products \(P_m \ \Box \ C_n\) and \(C_m \ \Box \ C_n\). In addition, we classify the graphs that attain some of the bounds mentioned in [10].

2. Path decomposition number of \(K_n-I\) and \(K_{n,n}-I\)

Theorem 2.1 [2] For even integers \(m\) and \(n\) with \(4 \leq m \leq n\), the graph \(K_n-I\) decomposes cycles of length \(m\) if and only if the number of edges in \(K_n-I\) is a multiple of \(m\)

Lemma 2.2. [11] Let \(m \equiv 2(mod \ 4)\), \(n \equiv 1(mod \ 2)\) and \(6 \leq m \leq 2n\). Then \(C_m |K_{n,n}-I\) if and only if \(m|n(n-1)\).

Theorem 2.3. Given the graph \(K_n-I\), where \(n\) is even, the minimum path decomposition number for \(K_n-I\) is \(\frac{n-2}{2}\).

Proof. The graph \(K_n-I\) has \(n\) vertices and \(\frac{n(n-2)}{2}\) edges. The largest cycle which is a subgraph of \(K_n-I\) is a cycle of order \(n\). Now, by Theorem 2.1, \(C_n |K_n-I\). We only need to know the number of copies \(C_n\) that can be gotten from \(K_n-I\), which is \(\frac{n-2}{2}\). Thus, we have \(\frac{n-2}{2}\) copies of \(C_n\) in \(K_n-I\). Therefore, \(\pi (K_n-I)=\frac{n-2}{2}\).

Lemma 2.4. If \(n \geq 4\) and an even integer, then \(K_{n,n}-I\) is \(\Big ( \frac{n-2}{2} C_{2n},nP_2 \Big )\)-decomposable.

Proof. Let \(X=\{1^1,2^1,3^1,...,n^1\}\) and \(Y=\{1^2,2^2,3^2,...,n^2\}\) form the column set of vertices in \(K_{n,n}-I\). Also, two vertices \(a^i\) and \(b^j\), has an edge in \(K_{n,n}-I\), if \(a \neq b\) and \(i \neq j\), \(i< j=2\). Since \(n\) is even, the degree of each vertex in \(K_{n,n}-I\) is odd.
Next, remove the edges $$ E(a^i, b^j)= \left\{\begin{array}{cc} (a,n-a+1) ,& \; a=1,2 \\ (a,a-2), & \; a=3,4,5,...,n \end{array}\right. ,a^i \in X, b^j \in Y $$ which are exactly \(n\) number of \(P_2\)'s. By removal of these edges, each vertex in \(K_{n,n}-I\) would be of even degree. In total, we have \(n(n-2)\) edges. At this point, we need to show that the subgraph \((K_{n,n}-I) \setminus E(a^i,b^j)\) admits a \(C_{2n}\) decomposition.
Now, by \(C_{2n}^r\), \(r \leq 1\), we mean the \(r^{th}\) copy of \(C_{2n}\) in \((K_{n,n}-I) \setminus E(a^i,b^j)\). With exception of \(C_{2n}^1\), all other \(C_{2n}^r\), \(r>1\), follow a similar pattern. The construction of these cycles of order \(2n\) is given below. \begin{align*} C_{2n}^1 & =1^1,2^2,3^1,4^2,...,(n-1)^1,n^2,(n-2)^1,(n-3)^2,(n-4)^1, (n-5)^2,\nonumber\\ & \ \ \ \ 2^1,1^2,n^1,(n-1)^2,1^1. \end{align*} For \(r=2,3,4,...,\frac{n-2}{2}\) we have that \begin{align*} C_{2n}^r & =1^1,(2r-1)^2,n^1,(2r-2)^2,(n-1)^1, (2r-3)^2,(n-2)^1,...,1^2, \nonumber\\ & \ \ \ \ (n-2r+2)^1,(n-1)^2,(n-2r+1)^1,n^2,(n-2r)^1,(n-2)^2, \nonumber\\ & \ \ \ \ (n-2r-1)^1,(n-3)^2,(n-2r-2)^1,(n-4)^2,...,(2r)^2,1^1. \end{align*} From the above construction, we conclude that the graph \((K_{n,n}-I) \setminus E(a^i,b^j)\) admits a \(C_{2n}\) decomposition. Clearly, \(r=\frac{n-2}{2}\) and thus \(C_{2n}|\big\{K_{n,n} -I \setminus E(a^i,b^j)\big \}=(C_{2n} \oplus C_{2n} \oplus C_{2n} \oplus \cdots \oplus \frac{n-2}{2} C_{2n} )\). Finally, we have that \(K_{n,n}-I\) is \(\Big ( \frac{n-2}{2} C_{2n},nP_2 \Big )\)-decomposable. Hence the proof.

Theorem 2.5. For the complete bipartite graph \(K_{n,n}-I\), we have that $$ \pi (K_{n,n}-I)= \left\{\begin{array}{cc} \frac{n-1}{2} ,& \; if \ n \ is \ odd \\ \frac{3n-2}{2} ,& \; otherwise \end{array}\right. $$

Proof. The graph \(K_{n,n}-I\) has \(2n\) vertices and \(n(n-1)\) edges. The largest cycle which is a subgraph of \(K_{n,n}-I\) is a cycle of order \(2n\). We now prove this theorem in two cases.

Case 1: when \(n\) is odd
By Lemma 2.2, \(C_{2n} |K_{n,n}-I\). We only need to know the number of copies of \(C_{2n}\) that can be obtained from \(K_{n,n}-I\), which is \(\frac{n-1}{2}\). Therefore, \(\pi (K_{n,n}-I)=\frac{n-1}{2}\).

Case 2: when \(n\) is even
By Lemma 2.4, the graph \(K_{n,n}-I\) can be decomposed into \(\frac{n-2}{2}\) copies of \(C_{2n}\) and \(n\) copies of \(P_2\). Since no vertex is repeated in these \(n\) copies of \(P_2\), we have that \(\pi (K_{n,n}-I)=\frac{3n-2}{2}\). The proof of this theorem is complete.

To end this section we now give the following remark. This remark is immediate from Theorem 2.3 and Theorem 2.5.

Remark 2.6. In [10], it was mentioned that every graph \(G\) which is Hamiltonian cycle decomposable attains the bound that \(\pi (G) \geq \lceil \frac{\Delta}{2} \rceil\). This is true as we see from Theorem 2.3 and Theorem 2.5 that the complete graph minus a one-factor and the complete bipartite graph \(K_{n,n}-I\), where \(n\) is odd, attains this bound. Now, when \(n\) is even in \(K_{n,n}-I\) we have \(\pi (K_{n,n}-I)=\frac{3\Delta+1}{2}\).

3. Path decomposition number of \(P_m \ \Box \ C_n\) and \(C_m \ \Box \ C_n\)

Theorem 3.1. Let \(m\) and \(n\) be positive integers then $$\pi(P_m \ \Box \ C_n )= \pi_a (P_m \ \Box \ C_n )=n$$.

Proof. First we give the construction of \(P_{mn}\) paths by constructing Hamilton paths of order \(n\) in each copy of \(C_n\) in \(P_m \ \Box \ C_n\). Let \(i\) be an odd number, in each copy of \(C_n^i\), join the end vertex of the Hamilton path in the \(i^{th}\) copy with the end vertex of the \(C_n^{i+1}\) copy of \(P_m \ \Box \ C_n\). Similarly, suppose \(i\) is even, in each copy of \(C_n^i\), join the first vertex of the Hamilton path in the \(i^{th}\) copy with the first vertex of the \(C_n^{i+1}\) copy of \(P_m \ \Box \ C_n\).

Next, for each internal vertex in the Hamilton path, join the vertices \(x_j^i\) and \(x_j^{i+1}\), \(1 \leq i \leq m\), \(i\) is calculated in modulo \(m\) and \(2 \leq j \leq n-1\). By this, we have \(n-2\) copies of \(P_m\) in \(P_m \ \Box \ C_n\).
Lastly, the left out edges which has not been covered by the path \(P_{mn}\) and the \(n-2\) copies of \(P_m\) form a path of order \(2m\). So we have that \(\pi(P_m \ \Box \ C_n)=\pi_a (P_m \ \Box \ C_n)=n\).

Remark 3.2. Since the Cartesian product of graph is commutative, the result in Theorem 3.1 holds for the graph \(C_m \ \Box \ P_n\) where \(m\) and \(n\) are positive integers.

Theorem 3.3. Let \(m\) and \(n\) be positive integers such that \(3 \leq n \leq m\), then \(\pi (C_m \ \Box \ C_n)=n\).

Proof. Since both \(m\) and \(n\) are positive integers, the proof of this theorem is split in two cases.

Case 1: when \(m\) is even and \(n \geq 3\).
First we give the construction of \(C_{mn}\) cycles by constructing Hamilton paths of order \(n\) in each copy of \(C_n\) in \(C_m \ \Box \ C_n\). Let \(i\) be an odd number, in each copy of \(C_n^i\), join the end vertex of the Hamilton path in the \(i^{th}\) copy with the end vertex of the \(C_n^{i+1}\) copy of \(C_m \ \Box \ C_n\). Similarly, suppose \(i\) is even, in each copy of \(C_n^i\), join the first vertex of the Hamilton path in the \(i^{th}\) copy with the first vertex of the \(C_n^{i+1}\) copy of \(C_m \ \Box \ C_n\).
Next, for each internal vertex in the Hamilton path, join the vertices \(x_j^i\) and \(x_j^{i+1}\), \(1 \leq i \leq m\), \(i\) is calculated in modulo \(m\) and \(2 \leq j \leq n-1\). By this, we have \(n-2\) copies of \(C_m \ \Box \ C_n\).
Now, notice that the left out edges which has not been covered by the cycle \(C_{mn}\) and the \(n-2\) copies of \(C_m\) form a cycle of order \(2m\). So we have that \(\pi (C_m \ \Box \ C_n)=n\).

Case 2: when \(m\) is odd and \(n \geq 3\).
Here, we first give the construction of \(C_{mn-1}\) cycles. For \(1 \leq i \leq m-2\), construct Hamilton paths of order \(n\) in each \(C_n^i\) copy in \(C_m \ \Box \ C_n\). Suppose \(i\) is odd, in each copy of \(C_n^i\) join the end vertex of the Hamilton path in the \(i^{th}\) copy with the end vertex of the \(C_n^{i+1}\) copy of \(C_m \ \Box \ C_n\). In the same way, if \(i\) is even, in each copy of \(C_n^i\) join the first vertex of the Hamilton path in the \(i^{th}\) copy of \(C_n^i\) with the first vertex of the \(C_n^{i+1}\) copy of \(C_m \ \Box \ C_n\). This gives a path of order \(n(m-2)\).
Next, let \(x\) be the first vertex in the \(C_n^{m-1}\) copy of \(C_m \ \Box \ C_n\). Now, construct a path \(P_{n-1}\) from \(C_n^{m-1} \setminus x\). Join the end vertex of \(C_n^{m-1}\) copy to the end vertex of \(C_n^{m-2}\) copy of \(C_m \ \Box \ C_n\). Since \(x\) is removed from \(C_n^{m-1}\), join the second vertex \(x_2^{m-1}\) of \(C_n^{m-1}\) to the second vertex \(x_2^m\) of \(C_n^m\) and then move in a clockwise direction to the first vertex in the \(m^{th}\) copy of \(C_m \ \Box \ C_n\). To get the desired \(C_{mn-1}\) cycle, join the first vertex \(x_1^m\) of \(C_n^m\) to \(x_1^1\) of \(C_n^1\) in the graph \(C_m \ \Box \ C_n\).
Furthermore, aside the second vertex, each internal vertex \(x_j^i\) and \(x_j^{i+1}\), \(1 \leq i \leq m\), \(i\) is calculated in modulo \(m\) and \(3 \leq j \leq n-1\) when joined in all other copies of \(C_n\) results to \(n-3\) copies of \(C_m\) in \(C_m \ \Box \ C_n\).
The left out edges which have not been covered by the cycle \(C_{mn-1}\) and the \(n-3\) copies of \(C_m\) form cycles \(C_{m+2}\) and \(C_{2m-1}\). We now give the construction of cycles \(C_{m+2}\) and \(C_{2m-1}\) as follows. By \(x_j^i\) we mean the \(j^{th}\) vertex of \(C_n\) in copy \(i\) of the graph \(C_m \ \Box \ C_n\). \begin{align*} C_{m+2}=x_2^1,x_2^2,x_2^3,...,x_2^{m-1},x_1^{m-1},x_1^m,x_2^m,x_2^1.\nonumber\\ C_{2m-1}=x_n^1,x_1^1,x_1^2,x_n^2,x_n^3,x_1^3,...,x_1^{m-1},x_n^{m-1},x_n^m,x_n^1.\nonumber \end{align*} Therefore we have that \(\pi (C_m \ \Box \ C_n)=n\). This completes the proof.

We now conclude this section with the following remark.

Remark 3.2. We note here in this section that although Arumugam et al. in [10] gave a relationship between the path decomposition number (or acyclic path decomposition number, as the case maybe) and the maximum degree \(\Delta\) of some graphs, we note that for the product \(G \ \Box \ H\) there is no such relationship since the parameters \(\pi (G \ \Box \ H)\) and \(\pi_a (G \ \Box \ H)\) do not depend on \(\Delta(G \ \Box \ H)\).

4. Conclusion and future work

So far in this work we have provided the path decomposition number for \(K_n-I\), \(K_{n,n}-I\) and the product \(P_m \ \Box \ C_n\) and \(C_m \ \Box \ C_n\). The question for determining the acyclic path decomposition number for these graphs certainly deserves attention. As a future work, we intend to provide the acyclic path decomposition number for these graphs and possibly look into other types of product graphs, e.g. lexicographic and tensor products.

Competing Interests

The authors declare that they have no competing interests.