Premium
Small cycle double covers of products I: Lexicographic product with paths and cycles
Author(s) -
Nowakowski R. J.,
Seyffarth K.
Publication year - 2008
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20265
Subject(s) - cartesian product , lexicographical order , combinatorics , mathematics , vertex (graph theory) , graph , product (mathematics) , cartesian coordinate system , discrete mathematics , geometry
Bondy conjectured that every simple bridgeless graph has a small cycle double cover (SCDC). We show that this is the case for the lexicographic products of certain graphs and along the way for the Cartesian product as well. Specifically, if G does not have an isolated vertex then G □ P 2 and G □ C 2k have SCDCs. If G has an SCDC then so does G □ P k , k > 2 and G □ C 2k + 1 . We use these Cartesian results to show that P 2j [ G ] ( j ≥ 1) and C k [G] (k ≠ 3, 5, 7) have SCDCs. Also, if G has an SCDC then so does P 2j + 1 [G] (j ≥ 4). The results for the lexicographic product are harder and, in addition to the Cartesian results, require certain decompositions of K n,n into perfect matchings. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 99–123, 2008