EDGE EXCHANGES IN HAMILTONIAN DECOMPOSITIONS OF KRONECKER-PRODUCT GRAPHS

Let G be a connected graph on n vertices, and let alpha, beta, gamma a nd delta be edge-disjoint cycles in G such that (i) alpha, beta (respe ctively, gamma, delta) are vertex-disjoint and (ii) \alpha\ + \beta\ = \gamma\ + \delta\ = n where \alpha\ denotes the length of alpha. We s ay that alpha, beta, gamma and delta yield two edge-disjoint Hamiltoni an cycles by edge exchanges if the four cycles respectively contain ed ges e, f, g and h such that each of (alpha - {e}) boolean OR (beta - { f}) boolean OR {g, h} and (gamma - {g}) boolean OR (delta - {h}) boole an OR {e,f} constitutes a Hamiltonian cycle in G. We show that if G is a nonbipartite, Hamiltonian decomposable graph on an even number of v ertices 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 amo ng smaller cycles in the product graph.