On the Hamiltonian property hierarchy of 3-connected planar graphs (Q2094888)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the Hamiltonian property hierarchy of 3-connected planar graphs |
scientific article |
Statements
On the Hamiltonian property hierarchy of 3-connected planar graphs (English)
0 references
8 November 2022
0 references
The prism over a graph \(G\) is the Cartesian product of \(G\) with the complete graph \(K_2\) and a graph \(G\) is said to be prism-Hamiltonian if the prism over \(G\) has a Hamilton cycle. A good even cactus is a connected graph in which every block is either an edge or an even cycle and every vertex is contained in at most two blocks. It is known that good even cacti are prism-Hamiltonian. \textit{S. Špacapan} [J. Comb. Theory, Ser. B 146, 364--371 (2021; Zbl 1457.05061)] asked whether having a spanning good even cactus is equivalent to having a Hamiltonian prism for 3-connected planar graphs. In this article, the author answers this question in the negative, by showing that there are infinitely many 3-connected planar prism-Hamiltonian graphs that have no spanning good even cactus. In addition, the existence of an infinite class of 3-connected planar graphs that have a spanning good even cactus but no spanning good even cactus with maximum degree three was proved.
0 references
3-connected planar graphs
0 references
Hamiltonian property hierarchy
0 references
prism Hamiltonicity
0 references
good even cactus
0 references