Decomposing 8-regular graphs into paths of length 4

2016/07/06 by Botler, Fábio, Talon, Alexandre
#05B40 #05C38 #05C51 #05C70 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1607.01456

Abstract

A T-decomposition of a graph G is a set of edge-disjoint copies of T in G that cover the edge set of G. Graham and Häggkvist (1989) conjectured that any 2ℓ-regular graph G admits a T-decomposition if T is a tree with ℓ edges. Kouider and Lonc (1999) conjectured that, in the special case where T is the path with ℓ edges, G admits a T-decomposition D where every vertex of G is the end-vertex of exactly two paths of D, and proved that this statement holds when G has girth at least (ℓ+3)/2. In this paper we verify Kouider and Lonc's Conjecture for paths of length 4.

Related

• Decompositions of highly connected graphs into paths of length five
• Approximate path decompositions of regular graphs
• Decomposing highly edge-connected graphs into paths of any given length
• Decomposition of (2k+1)-regular graphs containing special spanning 2k-regular Cayley graphs into paths of length 2k+1
• On path decompositions of 2k-regular graphs