Gallai’s Conjecture for Cartesian Product of Graphs

Abstract

Let $G$ be a connected graph of order $n$. Gallai conjectured that $G$ can be decomposed into $\frac{n+1}{2}$ paths. This is known as Gallai’s conjecture of path decomposition. In this paper, we focus on path decomposition of product graphs. It is proved that $G□H$ can be decomposed into $\frac{n(G□H)}{2}$ paths if $G$ is triangle-free and $∆(G)≤3$. This result implies that Gallai’s conjecture holds for this kind of graphs.