Multidecomposition of Cartesian Product of Some Graphs into Even Cycles and Matchings

Abstract

Let C2p and pK2 denote a cycle with 2p edges and p vertex-disjoint edges, respectively. For
graphs G , H′ and H′′ , a (H′, H′′) -multidecomposition of G is a partition of the edge set of G
into copies of H′ and copies of H′′ with at least one copy of H′ and at least one copy of H′′ .
In this paper, we investigate (C2p, pK2) -multidecomposition of the Cartesian product of paths,
cycles and complete graphs, for some values p ≥ 3 .