UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Cycle partitions of regular graphs

Gruslys, V; Letzter, S; (2020) Cycle partitions of regular graphs. Combinatorics, Probability and Computing 10.1017/S0963548320000553. (In press).

[img] Text
cycle-partition.pdf - Accepted version
Access restricted to UCL open access staff until 19 June 2021.

Download (411kB)

Abstract

Magnant and Martin conjectured that the vertex set of any d-regular graph G on n vertices can be partitioned into paths (there exists a simple construction showing that this bound would be best possible). We prove this conjecture when , improving a result of Han, who showed that in this range almost all vertices of G can be covered by vertex-disjoint paths. In fact our proof gives a partition of V(G) into cycles. We also show that, if 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
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 > 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
Downloads since deposit
1Download
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item