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 □ P₂ 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