The relation between Hamiltonian and 1-tough properties of the Cartesian product graphs

DOI10.1007/S00373-021-02292-YMaRDI QIDQ2045387zbMATH OpenOpenAlexFDO

Authors Louis Kao, Chih-Wen Weng

Publication date 12 August 2021

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.03084

zbMATH Keywords

Cartesian product graphgraph toughnessHamiltonian graphpath factor

Mathematics Subject Classification ID

Paths and cycles (05C38) Density (toughness, etc.) (05C42) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Abstract: The relation between Hamiltonicity and toughness of a graph is a long standing research problem. The paper studies the Hamiltonicity of the Cartesian product graph $G_{1}square{G}_2$ of graphs $G_1$ and $G_2$ satisfying that $G_1$ is traceable and $G_2$ is connected with a path factor. Let Pn be the path of order $n$ and $H$ be a connected bipartite graph. With certain requirements of $n$, we show that the following three statements are equivalent: (i) $P_{n}squareH$ is Hamiltonian; (ii) $P_{n}squareH$ is $1$-tough; and (iii) $H$ has a path factor.

Recommendations

• On the hamiltonicity of the Cartesian product
• Hamilton-connected properties in Cartesian product
• The Hamiltonian property and connectivity of the Cartesian product of infinite graphs
• Hamiltonicity and pancyclicity of Cartesian products of graphs
• scientific article; zbMATH DE number 1933225

Cites work

• 10-tough chordal graphs are Hamiltonian
• Hamiltonian circuits in certain prisms
• Hamiltonicity and pancyclicity of Cartesian products of graphs
• scientific article; zbMATH DE number 3141016 (Why is no real title available?)
• scientific article; zbMATH DE number 4087694 (Why is no real title available?)
• scientific article; zbMATH DE number 3720956 (Why is no real title available?)
• Non-hamiltonian 5 4-tough maximal planar graphs
• Not every 2-tough graph is Hamiltonian
• On the hamiltonicity of the Cartesian product
• Some Theorems on Abstract Graphs
• The Factorization of Linear Graphs
• Tough graphs and Hamiltonian circuits.

Cited in

(1)

• Hamiltonicity of Cartesian products of graphs

This page was built for publication: The relation between Hamiltonian and 1-tough properties of the Cartesian product graphs

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