For a graph \(G\), let \(la(G)\) denote the linear arboricity of \(G\) and \(\Delta(G)\) denote the maximum degree of \(G\). The famous linear arboricity conjecture was made by Akiyama, Exoo, and Harary [Covering and packing in graphs. IV. Linear arboricity] in 1981. It asserts that \(la(G) \leq \Bigl\lceil\frac{\Delta(G)+1}{2}\Bigr\rceil\). In this paper, we prove the linear arboricity conjecture for products of a path and a complete graph, and for products of a path and a tree.
In graph theory, a linear forest is a forest in which every component is a path. For a graph \(G\), the linear arboricity of \(G\) (defined by Harary [8] in 1970) is denoted by \(la(G)\) and is the minimum number of edge-disjoint linear forests whose union is \(E(G)\). The maximum degree of \(G\) is denoted by \(\Delta(G)\). We can observe \[\begin{aligned} \label{bound} la(G) \geq \left\lceil\frac{\Delta(G)}{2}\right\rceil. \end{aligned} \tag{1}\]
Also, it is well-known that, for regular graphs, \[\begin{aligned} \label{regularbound} la(G) \geq \left\lceil\frac{\Delta(G)+1}{2}\right\rceil. \end{aligned} \tag{2}\]
In 1981, Akiyama, Exoo, and Harary [2] made the famous linear arboricity conjecture:
Conjecture 1.1(Akiyama, Exoo, and Harary, [2]).For every graph \(G\), \[\begin{aligned} la(G) \leq \left\lceil\frac{\Delta(G)+1}{2}\right\rceil. \end{aligned}\]
This conjecture is still open, but it was proven for some graphs:
Theorem 1.2(Akiyama, Exoo, and Harary, [1]). For a complete graph \(K_n\), \[\begin{aligned} la(K_n)=\left\lceil\frac{n}{2}\right\rceil. \end{aligned}\]
Theorem 1.3(Akiyama, Exoo, and Harary, [1]).For a tree \(T\), \[\begin{aligned} la(T)=\left\lceil\frac{\Delta(T)}{2}\right\rceil. \end{aligned}\]
In 1992, Alon and Spencer [4] proved the following upper bound:
Theorem 1.4. (Alon and Spencer, [4]).For every graph \(G\), \[\begin{aligned} la(G) \leq \frac{\Delta(G)}{2}+O\Bigl(\Delta(G)^{\frac{2}{3}}log(\Delta(G))^{\frac{1}{3}}\Bigr). \end{aligned}\]
In 2020, Ferber, Fox, and Jain [6] proved the following improved upper bound:
Theorem 1.5(Ferber, Fox, and Jain [6]).For every graph \(G\), \[\begin{aligned} la(G) \leq \frac{\Delta(G)}{2}+C\Delta(G)^{\frac{2}{3}-\alpha}, \end{aligned}\] for constants \(C\) and \(\alpha\).
In this paper, we prove the linear arboricity conjecture for products of a path and a complete graph, and for products of a path and a tree.
For two graphs \(G_1\) and \(G_2\), the Cartesian product of them is denoted by \(G_1 \square G_2\), whose vertex set is \[\begin{aligned} V(G_1 \square G_2)=\{(v_1, v_2)\mid v_1\in V(G_1), v_2\in V(G_2)\}, \end{aligned}\] and edge set is \[\begin{aligned} E(G_1 \square G_2)=\{(v_1, v_2)(v_1', v_2')\mid v_1=v_1' \text{ and } v_2 v_2'\in E(G_2), \text{ or } v_1 v_1'\in E(G_1) \text{ and } v_2=v_2'\}. \end{aligned}\]
For two graphs \(G_1\) and \(G_2\), the direct product of them is denoted by \(G_1 \times G_2\), whose vertex set is \[\begin{aligned} V(G_1 \times G_2)=\{(v_1, v_2)\mid v_1\in V(G_1), v_2\in V(G_2)\}, \end{aligned}\] and edge set is \[\begin{aligned} E(G_1 \times G_2)=\{(v_1, v_2)(v_1', v_2')\mid v_1 v_1'\in E(G_1) \text{ and } v_2 v_2'\in E(G_2)\}. \end{aligned}\]
For two graphs \(G_1\) and \(G_2\), the strong product of them is denoted by \(G_1 \boxtimes G_2\), whose vertex set is \[\begin{aligned} V(G_1 \boxtimes G_2)=\{(v_1, v_2)\mid v_1\in V(G_1), v_2\in V(G_2)\}, \end{aligned}\] and edge set is \[\begin{aligned} E(G_1 \boxtimes G_2)=E(G_1 \square G_2)\cup E(G_1 \times G_2). \end{aligned}\]
In the following theorems, we assume \(n, m \geq 2\), because if \(n=1\), then the linear arboricity conjecture is proven by Theorem 1.2. If \(m=1\), then \(P_n \square K_1\) is only one path and \(P_n \times K_1\) does not have an edge.
In 2013, Tao and Lin [9] proved the linear arboricity conjecture for Cartesian product of a path and a complete graph.
Theorem 1.6(Tao and Lin, [9]).For Cartesian product of a path and a complete graph, \[\begin{aligned} la(P_n \square K_m)=\left\lceil\frac{m+1}{2}\right\rceil \leq \left\lceil\frac{\Delta(P_n \square K_m)+1}{2}\right\rceil, \end{aligned}\] for \(n, m \geq 2\).
In section 2, we first prove the following theorem, which proves the linear arboricity conjecture for direct product of a path and a complete graph.
Theorem 1.7. For direct product of a path and a complete graph, \[\begin{aligned} la(P_n \times K_m)=m-1=\left\lceil\frac{\Delta(P_n \times K_m)}{2}\right\rceil, \end{aligned}\] for \(n \geq 3\) and \(m \geq 2\). \[\begin{aligned} la(P_2 \times K_m)=\left\lceil\frac{m}{2}\right\rceil=\left\lceil\frac{\Delta(P_2 \times K_m)+1}{2}\right\rceil, \end{aligned}\] for \(m \geq 2\).
By combining Theorems 1.6 and 1.7, we further prove the following theorem for \(n \geq 3\), which proves the linear arboricity conjecture for strong product of a path and a complete graph. The case \(n=2\) is an open problem.
Theorem 1.8. For strong product of a path and a complete graph, \[\begin{aligned} la(P_n \boxtimes K_m)=\left\lceil\frac{3m-1}{2}\right\rceil=\left\lceil\frac{\Delta(P_n \boxtimes K_m)}{2}\right\rceil, \end{aligned}\] for \(n \geq 3\) and \(m \geq 2\).
In Section 3, we study Cartesian, direct, and strong products of a path \(P_n\) with \(n \geq 2\) and a tree \(T\). If \(n=1\), then the linear arboricity conjecture is proven by Theorem 1.3. In the following theorems, we assume \(\Delta(T)\) is even. The case \(\Delta(T)\) is odd is an open problem.
Theorem 1.9. For a path and a tree,
(a) \[\begin{aligned} la(P_n \square T)=\left\lceil\frac{\Delta(P_n \square T)}{2}\right\rceil, \end{aligned}\] for \(n \geq 2\) and even \(\Delta(T)\).
(b) \[\begin{aligned} la(P_n \times T)=\left\lceil\frac{\Delta(P_n \times T)}{2}\right\rceil, \end{aligned}\] for \(n \geq 2\) and even \(\Delta(T)\).
(c) \[\begin{aligned} la(P_n \boxtimes T)=\left\lceil\frac{\Delta(P_n \boxtimes T)}{2}\right\rceil, \end{aligned}\] for \(n \geq 2\) and even \(\Delta(T)\).
We first prove Theorem 1.7:
Proof of Theorem 1.7. Let \[\begin{aligned} V(P_n)=\{u_1, u_2, \dots, u_n\}, \end{aligned}\] and \[\begin{aligned} E(P_n)=\{u_1 u_2, u_2 u_3, \dots, u_{n-1} u_n\}. \end{aligned}\]
Let \[\begin{aligned} V(K_m)=\{v_1, v_2, \dots, v_m\}. \end{aligned}\] For convenience, we will also use notations \(v_{m+1}, v_{m+2}, \dots, v_{2m-1}\), which are defined by \(v_{m+1}=v_1\), \(v_{m+2}=v_2\), …, \(v_{2m-1}=v_{m-1}\).
We first assume \(n \geq 3\). So, for \(2 \leq k \leq n-1\) and \(1 \leq l \leq m\), the degree of \((u_k, v_l)\) is \(2m-2\). For \(k=1\) or \(k=n\) and \(1 \leq l \leq m\), the degree of \((u_k, v_l)\) is \(m-1\). So, in \(P_n \times K_m\), the maximum degree is \(2m-2\) and \(\left\lceil\frac{\Delta(P_n \times K_m)}{2}\right\rceil=m-1\).
We construct \(m-1\) linear forests by defining their edge sets as follows:
For \(1 \leq t \leq m-1\), let \[\begin{aligned} E_t=&\{(u_i, v_j)(u_{i+1}, v_{j+t})\mid 1 \leq i \leq n-1, i \text{ is odd}, 1 \leq j \leq m\}\\ &\cup\{(u_k, v_{l+t})(u_{k+1}, v_l)\mid 1 \leq k \leq n-1, k \text{ is even}, 1 \leq l \leq m\}. \end{aligned}\]
Then, the edges in \(E_t\) form a linear forest, which has \(m\) disjoint paths. If \(n\) is even, then these \(m\) disjoint paths are \[\begin{aligned} &\{(u_1, v_1), (u_2, v_{1+t}), (u_3, v_1), (u_4, v_{1+t}), \dots, (u_n, v_{1+t})\},\\ &\{(u_1, v_2), (u_2, v_{2+t}), (u_3, v_2), (u_4, v_{2+t}), \dots, (u_n, v_{2+t})\},\\ &\dots\\ &\{(u_1, v_m), (u_2, v_{m+t}), (u_3, v_m), (u_4, v_{m+t}), \dots, (u_n, v_{m+t})\}. \end{aligned}\]
If \(n\) is odd, then these \(m\) disjoint paths are \[\begin{aligned} &\{(u_1, v_1), (u_2, v_{1+t}), (u_3, v_1), (u_4, v_{1+t}), \dots, (u_n, v_1)\},\\ &\{(u_1, v_2), (u_2, v_{2+t}), (u_3, v_2), (u_4, v_{2+t}), \dots, (u_n, v_2)\},\\ &\dots\\ &\{(u_1, v_m), (u_2, v_{m+t}), (u_3, v_m), (u_4, v_{m+t}), \dots, (u_n, v_m)\}. \end{aligned}\]
The \(m-1\) linear forests cover all \(m(m-1)(n-1)\) edges in \(P_n \times K_m\), and each edge belongs to exactly one linear forest. So, \(la(P_n \times K_m) \leq m-1=\left\lceil\frac{\Delta(P_n \times K_m)}{2}\right\rceil\). By combining this result with (1), we get \(la(P_n \times K_m)=m-1=\left\lceil\frac{\Delta(P_n \times K_m)}{2}\right\rceil\).
We then assume \(n=2\). So, \(\Delta(P_2 \times K_m)=m-1=\Delta(K_m)\). We need to prove \(la(P_2 \times K_m)=\lceil\frac{m}{2}\rceil=\left\lceil\frac{\Delta(P_2 \times K_m)+1}{2}\right\rceil\).
For \(K_m\), assume the \(la(K_m)=\lceil\frac{m}{2}\rceil\) linear forests are \(F_1, F_2, \dots, F_{la(K_m)}\). For \(P_2 \times K_m\), we construct \(la(K_m)\) linear forests by defining their edge sets as follows:
For \(1 \leq t \leq la(K_m)\), let \[\begin{aligned} E_t=\{(u_i, v_j)(u_k, v_l)\mid u_i u_k\in E(P_2), v_j v_l\in E(F_t)\}. \end{aligned}\]
Then, the edges in \(E_t\) form a linear forest, which has twice as many paths as \(F_t\). So, \(la(P_2 \times K_m) \leq la(K_m)=\lceil\frac{m}{2}\rceil\). \(P_2 \times K_m\) is a regular graph. By combining this result with (2), we get \(la(P_2 \times K_m)=la(K_m)=\lceil\frac{m}{2}\rceil=\left\lceil\frac{\Delta(P_2 \times K_m)+1}{2}\right\rceil\). ◻
We combine Theorems 1.6 and 1.7 to prove Theorem 1.8:
Proof of Theorem 1.8. We assumed \(n \geq 3\). So, \(\Delta(P_n \boxtimes K_m)=3m-1\). By \(E(P_n \boxtimes K_m)=E(P_n \square K_m)\cup E(P_n \times K_m)\), we have \[\begin{aligned} la(P_n \boxtimes K_m)& \leq la(P_n \square K_m)+la(P_n \times K_m)\\ &=\left\lceil\frac{m+1}{2}\right\rceil+m-1\\ &=\left\lceil\frac{3m-1}{2}\right\rceil\\ &=\left\lceil\frac{\Delta(P_n \boxtimes K_m)}{2}\right\rceil. \end{aligned}\]
By combining this result with (1), we get \(la(P_n \boxtimes K_m)=\left\lceil\frac{\Delta(P_n \boxtimes K_m)}{2}\right\rceil\). ◻
In this section, we prove Theorem 1.9:
Proof of Theorem 1.9. Let \[\begin{aligned} V(P_n)=\{u_1, u_2, \dots, u_n\}, \end{aligned}\] and \[\begin{aligned} E(P_n)=\{u_1 u_2, u_2 u_3, \dots, u_{n-1} u_n\}. \end{aligned}\]
Let \[\begin{aligned} V(T)=\{v_1, v_2, \dots, v_m\}. \end{aligned}\]
(a) We first prove \[\begin{aligned} la(P_n \square T)=\left\lceil\frac{\Delta(P_n \square T)}{2}\right\rceil. \end{aligned}\]
If \(n \geq 3\), then \(\Delta(P_n \square T)=\Delta(T)+2\). We need to prove \(la(P_n \square T)=\lceil\frac{\Delta(T)+2}{2}\rceil=\frac{\Delta(T)}{2}+1\). (We assumed \(\Delta(T)\) is even.) If \(n=2\), then \(\Delta(P_n \square T)=\Delta(T)+1\). We still need to prove \(la(P_n \square T)=\lceil\frac{\Delta(T)+1}{2}\rceil=\frac{\Delta(T)}{2}+1\).
In Theorem 1.3, we have \(la(T)=\lceil\frac{\Delta(T)}{2}\rceil=\frac{\Delta(T)}{2}\). Assume the \(la(T)\) linear forests are \(F_1, F_2, \dots, F_{la(T)}\). For \(P_n \square T\), we construct \(\frac{\Delta(T)}{2}+1\) linear forests by defining their edge sets as follows:
For \(1 \leq t \leq la(T)=\frac{\Delta(T)}{2}\), let \[\begin{aligned} E_t=\{(u_i, v_j)(u_i, v_k)\mid 1 \leq i \leq n, 1 \leq j, k \leq m, v_j v_k\in E(F_t)\}. \end{aligned}\]
Let \[\begin{aligned} E_{\frac{\Delta(T)}{2}+1}=\{(u_i, v_j)(u_{i+1} v_j)\mid 1 \leq i \leq n-1, 1 \leq j \leq m\}. \end{aligned}\]
Our idea is: For \(1 \leq t \leq la(T)=\frac{\Delta(T)}{2}\), we let \(E_t\) be the set of edges in the \(n\) copies of \(F_t\). Then, we let \(E_{\frac{\Delta(T)}{2}+1}\) be the set of edges in the \(m\) copies of \(P_n\). So, the edges in each of \(E_1, E_2, \dots, E_{\frac{\Delta(T)}{2}+1}\) form a linear forest.
So, \(la(P_n \square T) \leq \frac{\Delta(T)}{2}+1=\lceil\frac{\Delta(P_n \square T)}{2}\rceil\). By combining this result with (1), we get \(la(P_n \square T)=\lceil\frac{\Delta(P_n \square T)}{2}\rceil\).
(b) We prove \[\begin{aligned} la(P_n \times T)=\left\lceil\frac{\Delta(P_n \times T)}{2}\right\rceil. \end{aligned}\]
We first assume \(n \geq 3\). So, \(\Delta(P_n \times T)=2\Delta(T)\). We need to prove \(la(P_n \times T)=\Delta(T)\).
In Theorem 1.3, we have \(la(T)=\lceil\frac{\Delta(T)}{2}\rceil=\frac{\Delta(T)}{2}\). (We assumed \(\Delta(T)\) is even.) Assume the \(la(T)\) linear forests are \(F_1, F_2, \dots, F_{la(T)}\). We divide the vertices in \(T\) into two parts \(V^+\) and \(V^-\):
We choose a vertex \(v\) and put it in \(V^+\). Then, every vertex with even distance from \(v\) is put in \(V^+\) and every vertex with odd distance from \(v\) is put in \(V^-\). Because \(T\) is a tree, every vertex in \(V^+\) is only adjacent to vertices in \(V^-\) and every vertex in \(V^-\) is only adjacent to vertices in \(V^+\).
For \(P_n \times T\), we construct \(2la(T)=\Delta(T)\) linear forests by defining their edge sets as follows:
For \(1 \leq t \leq la(T)=\frac{\Delta(T)}{2}\), let \[\begin{aligned} E_t^1=\{(u_i, v_j)(u_{i+1}, v_k)\mid 1 \leq i \leq n-1, v_j v_k\in E(F_t), v_j\in V^+, v_k\in V^-\}, \end{aligned}\] and \[\begin{aligned} E_t^2=\{(u_i, v_j)(u_{i+1}, v_k)\mid 1 \leq i \leq n-1, v_j v_k\in E(F_t), v_j\in V^-, v_k\in V^+\}. \end{aligned}\]
The edges in \(E_t^1\) form a linear forest, because, for every \(1 \leq i \leq n-1\), \(\{(u_i, v_j)(u_{i+1}, v_k)\mid v_j v_k\in E(F_t), v_j\in V^-, v_k\in V^+\}\) form a linear forest which is isomorphic to \(F_t\). If we take different \(i' \neq i\), then \(\{(u_{i'}, v_j)(u_{i'+1}, v_k)\mid v_j v_k\in E(F_t), v_j\in V^-, v_k\in V^+\}\) is disjoint with \(\{(u_i, v_j)(u_{i+1}, v_k)\mid v_j v_k\in E(F_t), v_j\in V^-, v_k\in V^+\}\). So, \(E_t^1\) is a linear forest, because it is a disjoint union of \(n-1\) linear forests.
Similarly, the edges in \(E_t^2\) also form a linear forest. So, \(la(P_n \times T) \leq 2la(T)=\Delta(T)\). By combining this result with (1), we get \(la(P_n \times T)=\Delta(T)=\lceil\frac{\Delta(P_n \times T)}{2}\rceil\).
We then assume \(n=2\). So, \(\Delta(P_n \times T)=\Delta(T)\). We need to prove \(la(P_n \times T)=\frac{\Delta(T)}{2}\), which can be proven by a similar construction: We construct \(E_t^1\) and \(E_t^2\) in the same way, and we can combine \(E_t^1\) and \(E_t^2\), because \(\{(u_1, v_j)(u_2, v_k)\mid v_j v_k\in E(F_t), v_j\in V^+, v_k\in V^-\}\) and \(\{(u_1, v_j)(u_2, v_k)\mid v_j v_k\in E(F_t), v_j\in V^-, v_k\in V^+\}\) are disjoint. So, \(E_t^1 \cup E_t^2\) form a linear forest when \(n=2\).
So, we get \(\frac{\Delta(T)}{2}\) linear forests and \(la(P_n \times T) \leq \frac{\Delta(T)}{2}\). By combining this result with (1), we get \(la(P_n \times T)=\frac{\Delta(T)}{2}\).
(c) We prove \[\begin{aligned} la(P_n \boxtimes T)=\left\lceil\frac{\Delta(P_n \boxtimes T)}{2}\right\rceil. \end{aligned}\]
We first assume \(n \geq 3\). So, \(\Delta(P_n \boxtimes T)=3\Delta(T)+2\). By \(E(P_n \boxtimes T)=E(P_n \square T)\cup E(P_n \times T)\), we have \[\begin{aligned} la(P_n \boxtimes T)& \leq la(P_n \square T)+la(P_n \times T)\\ &=\frac{\Delta(T)}{2}+1+\Delta(T)\\ &=\frac{3\Delta(T)+2}{2}\\ &=\left\lceil\frac{\Delta(P_n \boxtimes T)}{2}\right\rceil. \end{aligned}\]
By combining this result with (1), we get \(la(P_n \boxtimes T)=\left\lceil\frac{\Delta(P_n \boxtimes T)}{2}\right\rceil\).
We then assume \(n=2\). So, \(\Delta(P_n \boxtimes T)=2\Delta(T)+1\). By \(E(P_n \boxtimes T)=E(P_n \square T)\cup E(P_n \times T)\), we have \[\begin{aligned} la(P_n \boxtimes T)& \leq la(P_n \square T)+la(P_n \times T)\\ &=\frac{\Delta(T)}{2}+1+\frac{\Delta(T)}{2}\\ &=\frac{2\Delta(T)+2}{2}\\ &=\left\lceil\frac{2\Delta(T)+1}{2}\right\rceil\\ &=\left\lceil\frac{\Delta(P_n \boxtimes T)}{2}\right\rceil. \end{aligned}\]
By combining this result with (1), we get \(la(P_n \boxtimes T)=\left\lceil\frac{\Delta(P_n \boxtimes T)}{2}\right\rceil\). ◻
In this paper, we proved the linear arboricity conjecture for products of a path and a complete graph, and for products of a path and a tree. However, in Theorem 1.8, we assumed \(n \geq 3\). In Theorem 1.9, we assumed \(\Delta(T)\) is even. So, there are two open problems.
Problem 4.1(about Theorem 1.8).Prove the linear arboricity conjecture for \(P_n \boxtimes K_m\) when \(n=2\).
Problem 4.2(about Theorem 1.9).Prove the linear arboricity conjecture for \(P_n \square T\), \(P_n \times T\), and \(P_n \boxtimes T\) when \(\Delta(T)\) is odd.