Geodesic
On the Hamiltonian property hierarchy of 3-connected planar graphs
On-Hei Solomon Lo1
1Xiamen University
The electronic journal of combinatorics, Tome 29 (2022) no. 4

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl DOI arXiv
The prism over a graph $G$ is the Cartesian product of $G$ with the complete graph $K_2$. The graph $G$ is 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. Indeed, showing the existence of a spanning good even cactus has become the most common technique in proving prism-hamiltonicity. Špacapan [S. Špacapan. A counterexample to prism-hamiltonicity of 3-connected planar graphs. J. Combin. Theory Ser. B, 146:364--371, 2021] asked whether having a spanning good even cactus is equivalent to having a hamiltonian prism for 3-connected planar graphs. In this article we answer his 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, we prove 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.
DOI : 10.37236/11070
Classification : 05C10, 05C38, 05C45, 05C40, 05C76
Mots-clés : 3-connected planar graphs, Hamiltonian property hierarchy, prism Hamiltonicity, good even cactus

On-Hei Solomon Lo  1

1 Xiamen University 
On-Hei Solomon Lo. On the Hamiltonian property hierarchy of 3-connected planar graphs. The electronic journal of combinatorics, Tome 29 (2022) no. 4. doi: 10.37236/11070
@article{10_37236_11070,
     author = {On-Hei Solomon Lo},
     title = {On the {Hamiltonian} property hierarchy of 3-connected planar graphs},
     journal = {The electronic journal of combinatorics},
     year = {2022},
     volume = {29},
     number = {4},
     doi = {10.37236/11070},
     zbl = {1503.05028},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11070/}
}
TY  - JOUR
AU  - On-Hei Solomon Lo
TI  - On the Hamiltonian property hierarchy of 3-connected planar graphs
JO  - The electronic journal of combinatorics
PY  - 2022
VL  - 29
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11070/
DO  - 10.37236/11070
ID  - 10_37236_11070
ER  - 
%0 Journal Article
%A On-Hei Solomon Lo
%T On the Hamiltonian property hierarchy of 3-connected planar graphs
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/11070/
%R 10.37236/11070
%F 10_37236_11070

Cité par Sources :