排序方式: 共有8条查询结果,搜索用时 31 毫秒
1
1.
2.
利用收缩技术,证明了1)阶为n=2k且最小半度至少是k的有向图D是强哈密尔顿连通的,除非D属于某些图类;2)2强连通且包含n个顶点、(n-1)(n-2)+4条弧的有向图是强哈密尔顿连通的,除非D属于某些图类. 相似文献
3.
本文证明了:设G是n阶、k(≥3)连通无爪图,且不含同构于B的导出子图,若存在点v_0∈V(G),使d(v_0)≥n-2k+4,则G是Hamilton连通的. 相似文献
4.
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. 相似文献
5.
徐军 《数学的实践与认识》2010,40(24)
一个图G称为(X,Y)-free图,如果G不含同构于子图X和Y的导出子图.本文证明了X=K_(1,3)、Y∈{D,W,B}的3-连通(X,Y)-free图是Hamiltonian-连通的. 相似文献
6.
7.
《Discrete Mathematics》2022,345(8):112909
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. 相似文献
8.
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. 相似文献
1