Decomposing cubic graphs with low genus

Authors

Dong Ye, Middle Tennessee State University

Document Type

Lecture

Publication Date

10-10-2014

Abstract

It was conjectured by Ho man-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 graphs with low genus. Our method provides a polynomial time algorithm to nd the decomposition.

Relational Format

presentation

Recommended Citation

Ye, Dong, "Decomposing cubic graphs with low genus" (2014). Combinatorics Seminar. 48.
https://egrove.olemiss.edu/math_combinatorics/48