Long cycles and long paths in the Kronecker product of a cycle and a tree (Q1356512)

Denote by \(C_m \times T\) the Kronecker product of a cycle and a tree. It is known that \(C_m \times T\) is connected if \(m\) is odd and is made up of two isomorphic components if \(m\) is even. The authors construct a long cycle in each component of \(C_m \times T\) according to this schema: When \(T\) is the path \(P_n\), each component of the product can be decomposed into two long cycles. This is useful because Algorithm PF decomposes a tree with \(p\) leaves into a set of \(p-1\) paths (a ``path factor''). Using a path factor \(F\) of \(T\), Algorithm LC constructs a long cycle in \(C_m \times T\) for \(T\) with satisfactory vertex degrees, by joining long cycles obtained from the products of \(C_m\) with the paths of the factor.