Long cycles and long paths in the Kronecker product of a cycle and a tree
type: Item
instance of: scholarly article
title: Long cycles and long paths in the Kronecker product of a cycle and a tree
zbMATH Open document ID: 0872.05026
DOI: 10.1016/S0166-218X(96)00022-4
author: Pranava K. Jha
author: Naveen Agnihotri
author: Rajesh Kumar
published in: Discrete Applied Mathematics
publication date: 1997-09-25T00:00:00Z
full work available at URL: dam
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.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 1018587
zbMATH Keywords: Kronecker product graph
zbMATH Keywords: long cycle
zbMATH Keywords: long path
zbMATH Keywords: path factor
reviewed by: Norman F. Quimpo
MaRDI profile type: Publication
cites work: Hamiltonian cycles in the cartesian product of a tree and a cycle
cites work: Hamiltonian Cycles in Strong Products of Graphs
cites work: Cycles containing all vertices of maximum degree
cites work: Kronecker Products and Local Joins of Graphs
cites work: Q4198056
cites work: Parallel concepts in graph theory
cites work: Q5621382
cites work: Associative products of graphs
cites work: Decompositions of the Kronecker product of a cycle and a path into long cycles and long paths
cites work: Q5286479
cites work: Q3356326
cites work: Path coverings of the vertices of a tree
cites work: Q3743340
cites work: The Kronecker Product of Graphs
description: scientific article; zbMATH DE number 1018587