Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653342 | European Journal of Combinatorics | 2016 | 7 Pages |
Abstract
It was conjectured by Hoffmann-Ostenhof that the edge set of every cubic graph can be decomposed into a spanning tree, a matching and a family of cycles. We prove the conjecture for 3-connected cubic plane graphs and 3-connected cubic graphs on the projective plane. Our proof provides a polynomial time algorithm to find the decomposition for 3-connected cubic plane graphs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Kenta Ozeki, Dong Ye,