


Next: Nabil Shalaby - Skolem Up: Discrete Mathematics / Mathématiques Previous: Suzanne Seager - Variants
Karen Seyffarth - Small cycle double covers of line graphs
KAREN SEYFFARTH, Department of Mathematics and Statistics, University of Calgary, Calgary, Alberta T2N 1N4, Canada | |
Small cycle double covers of line graphs |
A cycle double cover of a graph, G, is a collection of
cycles, such that every edge of G lies in precisely two
cycles of
. If G is simple and has at most n vertices,
then a cycle double cover of G may require as many as n-1 cycles,
and we say that
is a small cycle double cover
(
) of G if
contains at most n-1 cycles. The
Small Cycle Double Cover Conjecture, due to J. A. Bondy, states that
every simple bridgeless graph has an SCDC, and is a strengthening of
the well-known Cycle Double Cover Conjecture. I will describe
some recent work with G. MacGillivray on proving the
Conjecture
for certain line graphs, in particular, line graphs of complete graphs,
complete bipartite graphs, and planar graphs. The techniques used in
these proofs can also be used to verify the
Conjecture for some
other types of line graphs.



Next: Nabil Shalaby - Skolem Up: Discrete Mathematics / Mathématiques Previous: Suzanne Seager - Variants eo@camel.math.ca