P K Jha, Naveen Agnihotri and Rajesh Kumar. 1996. On edge exchanges in Hamiltonian Decompositions of Kronecker-product graphs. Computers and Mathematics with Applications. 31(2):11-19.


Let G be a connected graph on n vertices, and let &alpha, &beta, &gamma and &delta be edge-disjoint cycles in G such that (i) &alpha &beta (resp. &gamma, &delta) are vertex-disjoint and (ii) |&alpha|+|&beta| = |&gamma|+|&delta| = n, where |&alpha| denotes the length of &alpha. We say that &alpha, &beta, &gamma and &delta 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 (&alpha - {e}) U (&beta - {f}) U {g, h} and (&gamma - {g}) U (&delta -{h}) U {e, f} constitutes a hamiltonian cycle in G. We show that if G is a non-bipartite, 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 of a hamiltonian decomposition by means of appropriate edge exchanges among smaller cycles in the product graph.