Gruslys, V;
Letzter, S;
(2021)
Cycle partitions of regular graphs.
Combinatorics, Probability and Computing
, 30
(4)
pp. 526-541.
10.1017/S0963548320000553.
Preview |
Text
cycle-partition.pdf - Accepted Version Download (411kB) | Preview |
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 = (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 = (n) and G is bipartite, then V(G) can be partitioned into n/(2d) paths (this bound is tight for bipartite graphs).
| Type: | Article |
|---|---|
| Title: | Cycle partitions of regular graphs |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1017/S0963548320000553 |
| Publisher version: | https://doi.org/10.1017/S0963548320000553 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10107283 |
Archive Staff Only
 |
View Item |
