Cycle partitions of regular graphs

Abstract

Magnant and Martin conjectured that the vertex set of any $d$-regular graph $G$ on $n$ vertices can be partitioned into $n/(d+1)$ paths (there exists a simple construction showing that this bound would be best possible). We prove this conjecture when $d=\Omega (n)$, improving a result of Han, who showed that in this range almost all vertices of $G$ can be covered by $n/(d+1)+1$ vertex-disjoint paths. In fact, our proof gives a partition of $V(G)$ into cycles. We also show that, if $d=\Omega (n)$ and $G$ is bipartite, then $V(G)$ can be partitioned into $n/(2d)$ paths (this bound in tight for bipartite graphs).

31 pages, 1 figure

Cited by in corpus (2)

• Random perfect matchings in regular graphs
• Cycle Partitions in Dense Regular Digraphs and Oriented Graphs