Kronecker products of paths and cycles: Decomposition, factorization and bi-pancyclicity (Q1379832): Difference between revisions

In the Kronecker product \(G\times H\) of graphs \(G\) and \(H\), \(\{(u,x),(v,y)\}\) is an edge if \(\{u,v\}\) and \(\{x,y\}\) are edges of \(G\) and \(H\), respectively. If \(m\) is even and \(n\equiv 0\pmod 4\) then the odd component of \(P_{m+1}\times P_{n+1}\) is edge decomposable into cycles of uniform length \(rs\), where \(r\) and \(s\) are suitable divisors of \(m\) and \(n\), respectively. Similar results are obtained for the edge decomposition of the components of the products of cycles with paths and other cycles. Other results factorize \(C_{2i+1}\times C_{2j+1}\) into shortest odd cycles and the components of \(C_{4i}\times C_{4j}\) into 4-cycles. Finally, each component of \(C_m\times C_{4j}\), which is bipartite, has an ordering of its vertices in which all even cycles of length \(\geq 4\) appear.