Kronecker products of paths and cycles: Decomposition, factorization and bi-pancyclicity
type: Item
instance of: scholarly article
title: Kronecker products of paths and cycles: Decomposition, factorization and bi-pancyclicity
zbMATH Open document ID: 0890.05052
DOI: 10.1016/S0012-365X(97)00138-6
author: Pranava K. Jha
published in: Discrete Mathematics
publication date: 1998-03-24T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1121492
zbMATH Keywords: Kronecker product
zbMATH Keywords: edge decomposition
zbMATH Keywords: factorization
zbMATH Keywords: bi-pancyclicity
reviewed by: Norman F. Quimpo
MaRDI profile type: Publication
cites work: Q3197858
cites work: Pancyclic graphs. I
cites work: Decompositions of the Kronecker product of a cycle and a path into long cycles and long paths
cites work: Q5688100
cites work: Factorisations of 4-regular graphs and Petersen's theorem
cites work: Factorizations of product graphs into cycles of uniform length
cites work: Pancyclicity and extendability in strong products
cites work: Bipartite graphs with cycles of all even lengths
cites work: Q3697041
cites work: Q4713103
full work available at URL: s0012-365x(97)00138-6
OpenAlex ID: W2140526538
Recommended article: Decompositions of the Kronecker product of a cycle and a path into long cycles and long paths
Recommended article: Q5197610
Recommended article: Cycle Decompositions of $K_{\lowercase{n,n}}-I$
Recommended article: Long cycles and long paths in the Kronecker product of a cycle and a tree
Recommended article: Cycle decompositions of \(K_n\) and \(K_n-I\)
Recommended article: Factorizations of the product of cycles
Recommended article: Q3635585
Recommended article: Q3070206
Recommended article: Q4487447
Recommended article: Decomposition of the product of cycles based on degree partition
description: scientific article; zbMATH DE number 1121492