Decomposition of the Product of Cycles Based on Degree Partition

Abstract

The Cartesian product of n cycles is a 2n-regular, 2n-connected and bi- pancyclic graph. Let G be the Cartesian product of n even cycles and let 2n = n1+ n2+ ・ ・ ・ + nkwith k ≥ 2 and ni≥ 2 for each i. We prove that if k = 2, then G can be decomposed into two spanning subgraphs G1and G2such that each Giis ni-regular, ni-connected, and bipancyclic or nearly bipancyclic. For k > 2, we establish that if all niin the partition of 2n are even, then G can be decomposed into k spanning subgraphs G1,G2, . . . ,Gk such that each Giis ni-regular and ni-connected. These results are analo- gous to the corresponding results for hypercubes.

Keywords

• hypercube
• cartesian product
• n-connected
• regular
• bipan- cyclic
• spanning subgraph
• 05c40
• 05c70
• 68r10