Cycle Double Covers Containing Predefined 2-Regular Subgraphs

Importance: High ✭✭✭
Subject: Graph Theory
Keywords:
Recomm. for undergrads: no
Posted by: arthur
on: June 21st, 2017
Conjecture   Let $ G $ be a $ 2 $-connected cubic graph and let $ S $ be a $ 2 $-regular subgraph such that $ G-E(S) $ is connected. Then $ G $ has a cycle double cover which contains $ S $ (i.e all cycles of $ S $).

Used definitions in the above conjecture: a "cycle" is a connected 2-regular subgraph, a "cycle double cover" of a graph $ G $ is a set of cycles of $ G $ such that every edge of $ G $ is contained in precisely two cycles of the set. This conjecture has been motivated by Theorem 3, respectively, Theorem 4 in www.arxiv.org/abs/1711.10614. A weaker conjecture (Conjecture 14) has been stated in "Snarks with special spanning trees" (see www.arxiv.org/abs/1706.05595).