Decompositions of the Kronecker product of a cycle and a path into long cycles and long paths (Q1196378): Difference between revisions

The author studies the Kronecker product of a cycle and a path, where the Kronecker product \(G\times H\) of graphs \(G=(V,E)\) and \(H=(W,F)\) is defined as follows: \[ V(G\times H)=V\times W, \] \[ E(G\times H)=\bigl\{\{(ux), (v,y)\}: \{u,v\}\in E\quad\text{and}\quad\{x,y\}\in F\bigr\}. \] Decompositions of \(C_ m\times P_ n\) into long paths and long cycles are presented, and these decompositions give bounds on the lengths of a longest path and a longest cycle in \(C_ m\times P_ n\). For paths of even order, these bounds are shown to be sharp and it is conjectured that the bounds are sharp in all cases.