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
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 
@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
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

Cité par Sources :