Regular Path Decompositions of Odd Regular Graphs

摘要

Kotzig asked in 1979 what are necessary and sufficient conditions for a d-regular simple graph to admit a decomposition into paths of length d for odd d>3. For cubic graphs, the existence of a 1-factor is both necessary and sufficient. Even more, each 1-factor is extendable to a decomposition of the graph into paths of length 3 where the middle edges of the paths coincide with the 1-factor. We conjecture that existence of a 1-factor is indeed a sufficient condition for Kotzig's problem. For general odd regular graphs, most 1-factors appear to be extendable and we show that for the family of simple 5-regular graphs with no cycles of length 4, all 1-factors are extendable. However, for d>3 we found infinite families of d-regular simple graphs with non-extendable 1-factors. Few authors have studied the decompositions of general regular graphs. We present examples and open problems; in particular, we conjecture that in planar 5-regular graphs all 1-factors are extendable.