Abstract
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 K1, a K2, 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 K2 or a cycle, and that any connected graph G ≠ K1 with maximal degree at most 3 contains a spanning forest F without isolated vertices for which every component of G-E(F) is a K1, a K2 or a cycle. We also prove a related statement about path-factorizations of graphs with maximal degree 3.
| Original language | English |
|---|---|
| Pages (from-to) | 1322-1327 |
| Number of pages | 6 |
| Journal | Discrete Mathematics |
| Volume | 338 |
| Issue number | 8 |
| DOIs | |
| State | Published - 6 Aug 2015 |
Keywords
- Graph factorization
- Path-factorization
- Spanning tree
Fingerprint
Dive into the research topics of 'Decompositions of graphs into trees, forests, and regular subgraphs'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver