Gallai's path decomposition conjecture for cartesian product of graphs (\uppercase\expandafter{\romannumeral 2})

Abstract

Let $G$ be a graph of order $n$. A path decomposition $\mathcal{P}$ of $G$ is a collection of edge-disjoint paths that covers all the edges of $G$. Let $p(G)$ denote the minimum number of paths needed in a path decomposition of $G$. Gallai conjectured that if $G$ is connected, then $p(G)\le \lceil \frac{n}{2}\rceil$. In this paper, we prove that Gallai's path decomposition conjecture holds for the cartesian product $G\square H$, where $H$ is any graph and $G$ is a unicyclic graph or a bicyclic graph.

arXiv comment26 pages, 2 figures. arXiv admin note: text overlap with arXiv:2310.11189