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

DOI10.1007/S00373-021-02292-YzbMATH Open1470.05095arXiv2003.03084OpenAlexW3134355371MaRDI QIDQ2045387FDOQ2045387

Authors: Louis Kao, Chih-Wen Weng 

Publication date: 12 August 2021

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

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.

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

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

zbMATH Keywords

Hamiltonian graphCartesian product graphpath factorgraph toughness

Mathematics Subject Classification ID

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

Cites Work

• The Factorization of Linear Graphs
• Title not available (Why is that?)
• Some Theorems on Abstract Graphs
• Not every 2-tough graph is Hamiltonian
• Tough graphs and Hamiltonian circuits.
• 10-tough chordal graphs are Hamiltonian
• On the hamiltonicity of the Cartesian product
• Title not available (Why is that?)
• Hamiltonicity and pancyclicity of Cartesian products of graphs
• Non-hamiltonian \(5 \over 4\)-tough maximal planar graphs
• Hamiltonian circuits in certain prisms
• Title not available (Why is that?)

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)