On path decompositions of 2k-regular graphs

Abstract

Tibor Gallai conjectured that the edge set of every connected graph $G$ on $n$ vertices can be partitioned into $\lceil n/2\rceil$ paths. Let ${\mathcal{G}}_k$ be the class of all $2k$-regular graphs of girth at least $2k-2$ that admit a pair of disjoint perfect matchings. In this work, we show that Gallai's conjecture holds in ${\mathcal{G}}_k$, for every $k\ge 3$. Further, we prove that for every graph $G$ in ${\mathcal{G}}_k$ on $n$ vertices, there exists a partition of its edge set into $n/2$ paths of lengths in $\{2k-1,2k,2k+1\}$.