Edge exchanges in hamiltonian decompositions of Kronecker-product graphs

AbstractLet G be a connected graph on n vertices, and let α, β, γ and δ be edge-disjoint cycles in G such that 1.(i) α, β (respectively, γ, δ) are vertex-disjoint and2.(ii) |Ga| + |β| = |γ| + |δ| = n, where |α| denotes the length of α. We say that α, β, γ and δ yield two edge-disjoint Hamiltonian cycles by edge exchanges if the four cycles respectively contain edges e, f, g and h such that each of (α−e) ∪ g,h and (γ−g) ∪ e,f constitutes a Hamiltonian cycle in G. We show that if G is a nonbipartite, Hamiltonian decomposable graph on an even number of vertices which satisfies certain conditions, then Kronecker product of G and K2 as well as Kronecker product of G and an even cycle admits a Hamiltonian decomposition by means of appropriate edge exchanges among smaller cycles in the product graph