LONG CYCLES AND LONG PATHS IN THE KRONECKER PRODUCT OF A CYCLE AND A TREE

Let C-m x T denote the Kronecker product of a cycle C-m and a tree T. If m is odd, then C-m x T is connected, otherwise this graph consists of two isomorphic components. This paper presents a scheme which const ructs a long cycle in each component of C-m x T. If T satisfies certai n degree constraints, then the cycle thus traced is shown to be a domi nating set, and in some cases, a vertex cover of that component. The p rocedure builds on (i) results on longest cycles in C-m x P-n, and (ii ) a path factor of T. Additional results include characterizations for the existence of a Hamiltonian cycle and for that of a Hamiltonian pa th in C-m x T.