Hamiltonicity of Cartesian products of graphs
In this paper, the authors prove that for every \(\Delta\ge 3\) there exits a graph (actually a tree) \(G\) of maximum degree \(\Delta\) and containing a path factor, such that the Cartesian product \(G\,\square\,P_m\) is not Hamiltonian for every \(m\le 4\Delta -3\). This result resolves a conjecture due \textit{L. Kao} and \textit{C.-w. Weng} posed in [ibid. 37, No. 3, 933--943 (2021; Zbl 1470.05095)], where on the other hand it is proved that if a tree \(T\) of maximum degree \(\Delta\) has a path factor, \(m\) is even and \(m\ge 4\Delta -2\), then \(T\,\square\, P_m\) is Hamiltonian.
- Hamilton cycles in prisms
- Hamiltonian Cycles in Products of Graphs
- Hamiltonian cycles in the cartesian product of a tree and a cycle
- Hamiltonicity and pancyclicity of Cartesian products of graphs
- scientific article; zbMATH DE number 3720956 (Why is no real title available?)
- scientific article; zbMATH DE number 17510 (Why is no real title available?)
- Not every 2-tough graph is Hamiltonian
- On the hamiltonicity of the Cartesian product
- Perfect matchings and Hamiltonicity in the Cartesian product of cycles
- Recent advances on the Hamiltonian problem: survey III
- The relation between Hamiltonian and 1-tough properties of the Cartesian product graphs
- Tough graphs and Hamiltonian circuits.
This page was built for publication: Hamiltonicity of Cartesian products of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6873551)
