Decompositions of graphs into trees, forests, and regular subgraphs

作者：Akbari Saieed; Jensen Tommy R^*; Siggers Mark

来源：Discrete Mathematics, 2015, 338(8): 1322-1327.

DOI：10.1016/j.disc.2015.02.021

• Graph factorization
• Spanning tree
• Path-factorization

A conjecture by A. Hoffmann-Ostenhof suggests that any connected cubic graph G contains a spanning tree T for which every component of G - E(T) is a K-1, a K-2, or a cycle. We show that any cubic graph G contains a spanning forest F for which every component of G - E(F) is a K-2 or a cycle, and that any connected graph G not equal K-1 with maximal degree at most 3 contains a spanning forest F without isolated vertices for which every component of G - E(F) is a K-1, a K-2 or a cycle. We also prove a related statement about path-factorizations of graphs with maximal degree 3.

• 出版日期2015-8-6