Decompositions of graphs into trees, forests, and regular subgraphs

Saieed Akbari, Tommy R. Jensen, Mark Siggers

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

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 languageEnglish
Pages (from-to)1322-1327
Number of pages6
JournalDiscrete Mathematics
Volume338
Issue number8
DOIs
StatePublished - 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