Decomposition of the product of cycles based on degree partition
Y. M. Borse, S. R. Shaikh · Discussiones Mathematicae Graph Theory · 2018
The Cartesian product of n cycles is a 2n-regular, 2n-connected and bipancyclic graph. Let G be the Cartesian product of n even cycles and let 2n = n 1 + n 2 + + n k with k 2 and n i 2 for each i. We prove that if k = 2, then G can be decomposed into two spanning subgraphs G 1 and G 2 such that each G i is n i -regular, n i -connected, and bipancyclic or nearly bipancyclic. For k > 2, we establish that if all n i in the partition of 2n are even, then G can be decomposed into k spanning subgraphs G 1 , G 2 , . . . , G k such that each G i is n i -regular and n i -connected. These results are analogous to the corresponding results for hypercubes.