Article ID Journal Published Year Pages File Type
4649470 Discrete Mathematics 2009 5 Pages PDF
Abstract

Suppose that a 2-connected cubic graph GG of order nn has a circuit CC of length at least n−4n−4 such that G−V(C)G−V(C) is connected. We show that GG has a circuit double cover containing a prescribed set of circuits which satisfy certain conditions. It follows that hypohamiltonian cubic graphs (i.e., non-hamiltonian cubic graphs GG such that G−vG−v is hamiltonian for every v∈V(G)v∈V(G)) have strong circuit double covers.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,