Yang Zhang

Gallai’s Conjecture for Cartesian Product of Graphs

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$...