On path decompositions of 2k-regular graphs

2015/10/08 by Botler, Fábio, Jiménez, Andrea · 1 citation
#05B40 #05C38 #05C51 #05C70 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1510.02526

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 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 G_k, for every k ≥ 3. Further, we prove that for every graph G in 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\.

Cited by

• Path decompositions of Eulerian graphs

Related

• Gallai's path decomposition in planar graphs
• Decomposition of (2k+1)-regular graphs containing special spanning 2k-regular Cayley graphs into paths of length 2k+1
• On Gallai's and Hajós' Conjectures for graphs with treewidth at most 3
• Decomposing 8-regular graphs into paths of length 4
• Gallai's path decomposition conjecture for triangle-free planar graphs