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

DOI10.1016/S0166-218X(96)00022-4MaRDI QIDQ1356512zbMATH OpenFDO

Authors Pranava K. Jha, Naveen Agnihotri, Rajesh Kumar

Publication date 25 September 1997

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

Kronecker product graphlong cyclelong pathpath factor

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Review text

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.

Recommendations

• Decompositions of the Kronecker product of a cycle and a path into long cycles and long paths
• Kronecker products of paths and cycles: Decomposition, factorization and bi-pancyclicity
• Cycle Kronecker products that are representable as optimal circulants
• scientific article; zbMATH DE number 969983

Cites work

• Associative products of graphs
• Cycles containing all vertices of maximum degree
• Decompositions of the Kronecker product of a cycle and a path into long cycles and long paths
• Hamiltonian Cycles in Strong Products of Graphs
• Hamiltonian cycles in the cartesian product of a tree and a cycle
• scientific article; zbMATH DE number 4208106 (Why is no real title available?)
• scientific article; zbMATH DE number 3977047 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 224058 (Why is no real title available?)
• scientific article; zbMATH DE number 3345462 (Why is no real title available?)
• Kronecker Products and Local Joins of Graphs
• Parallel concepts in graph theory
• Path coverings of the vertices of a tree
• The Kronecker Product of Graphs

Cited in

(3)

• Decompositions of the Kronecker product of a cycle and a path into long cycles and long paths
• Kronecker products of paths and cycles: Decomposition, factorization and bi-pancyclicity
• \([r,s,t]\)-colorings of graph products

This page was built for publication: Long cycles and long paths in the Kronecker product of a cycle and a tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1356512)