强哈密尔顿连通有向图的一个注记

利用收缩技术,证明了1)阶为n=2k且最小半度至少是k的有向图D是强哈密尔顿连通的,除非D属于某些图类;2)2强连通且包含n个顶点、(n-1)(n-2)+4条弧的有向图是强哈密尔顿连通的,除非D属于某些图类.     

无爪图的次与Hamilton连通性

本文证明了：设G是n阶、k（≥3）连通无爪图，且不含同构于B的导出子图，若存在点v_0∈V（G），使d（v_0）≥n-2k＋4，则G是Hamilton连通的．     

Hamiltonian properties of polyhedra with few 3-cuts—A survey

We give an overview of the most important techniques and results concerning the hamiltonian properties of planar 3-connected graphs with few 3-vertex-cuts. In this context, we also discuss planar triangulations and their decomposition trees. We observe an astonishing similarity between the hamiltonian behavior of planar triangulations and planar 3-connected graphs. In addition to surveying, (i) we give a unified approach to constructing non-traceable, non-hamiltonian, and non-hamiltonian-connected triangulations, and show that planar 3-connected graphs (ii) with at most one 3-vertex-cut are hamiltonian-connected, and (iii) with at most two 3-vertex-cuts are 1-hamiltonian, filling two gaps in the literature. Finally, we discuss open problems and conjectures.     

3-连通(X,Y)-free图的Hamiltonian-连通性

一个图G称为(X,Y)-free图,如果G不含同构于子图X和Y的导出子图.本文证明了X=K_(1,3)、Y∈{D,W,B}的3-连通(X,Y)-free图是Hamiltonian-连通的.     

Every 3-connected claw-free graph with domination number at most 3 is hamiltonian-connected

We prove that every 3-connected claw-free graph with domination number at most 3 is hamiltonian-connected. The result is sharp and it is inspired by a conjecture posed by Zheng, Broersma, Wang and Zhang in 2020.     

Proper interval graphs and the guard problem

This paper is a study of the hamiltonicity of proper interval graphs with applications to the guard problem in spiral polygons. We prove that proper interval graphs with 2 vertices have hamiltonian paths, those with 3 vertices have hamiltonian cycles, and those with 4 vertices are hamiltonian-connected if and only if they are, respectively, 1-, 2-, or 3-connected. We also study the guard problem in spiral polygons by connecting the class of nontrivial connected proper interval graphs with the class of stick-intersection graphs of spiral polygons.