Bibliography

Pranava K Jha, Naveen Agnihotri and Rajesh Kumar. 1997. Long cycles and long paths in the Kronecker product of a cycle and a tree. Discrete Applied Mathematics. 74(2):101-121.

Abstract

Let Cm × T denote the Kronecker product of a cycle Cm and a tree T. If m is odd, then Cm × T is connected, otherwise this graph consists of two isomorphic components. This paper presents a scheme which constructs a long cycle in each component of Cm × T, where T satisfies certain degree constraints. The cycle thus traced is shown to be a dominating set, and in some cases, a vertex cover of that component. The algorithm builds on (i) results on longest cycles in Cm × Pn, where Pn is a path on n vertices, and (ii) a path factorization of T. Additional results include characterizations for the existence of a Hamiltonian cycle and for that of a Hamiltonian path in Cm × T.


naveen@bhalu.com