Small cycle double covers of products I: Lexicographic product with paths and cycles

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 square P-2 and G square C-2k have SCDCs. If G has an SCDC then so does G square P-k, k > 2 and G square C2k+1. We use these Cartesian results to show that P-2j[G] (j >= 1) and C-k[G] (k not equal,4 3, 5, 7) have SCDCs. Also, if G has an SCDC then so does P2j+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,K-n into perfect matchings. (C) 2007 Wiley Periodicals, Inc.