Cycle partitions of regular graphs. (18th July 2021)

• Record Type: Journal Article
• Authors: Gruslys, Vytautas; Letzter, Shoham
• Is Part Of: Combinatorics, probability and computing. Volume 30:Number 4(2021)
• Page Start: 526
• Page End: 549
• Publication Date: 2021-07-18
• Subjects: 05C70 -- 05C38; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548320000553
• Languages: English
• ISSNs: 0963-5483

Abstract

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 /(2 d ) paths (this bound is tight for bipartite graphs).