Premium
Regular path decompositions of odd regular graphs
Author(s) -
Favaron Odile,
Genest François,
Kouider Mekkia
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20413
Subject(s) - mathematics , combinatorics , conjecture , simple (philosophy) , planar graph , discrete mathematics , 1 planar graph , indifference graph , pathwidth , strongly regular graph , modular decomposition , graph , chordal graph , line graph , philosophy , epistemology
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. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 114–128, 2010