Fleischner, H., Häggkvist, R., & Hoffmann-Ostenhof, A. (2019). Cycle Double Covers via Kotzig Graphs. Journal of Combinatorial Theory, Series B, 135, 212–226. https://doi.org/10.1016/j.jctb.2018.08.005
Theoretical Computer Science; Computational Theory and Mathematics; Discrete Mathematics and Combinatorics; Cubic graph 3-regular graph Cycle double cover Frame Kotzig graph
-
Abstract:
We show that every 2-connected cubic graph G has a cycle double cover if G has a spanning subgraph F such that (i) every component of F has an even number of vertices (ii) every component of F is either a cycle or a subdivision of a Kotzig graph and (iii) the components of F are connected to each other in a certain general manner.