设$t$是一个非负实数,$G$是一个图,$S$是$V (G)$的一个子集,$c (G-S)$表示$G-S$中连通分支的个数。如果对任意$S\subseteq V (G)$都存在$t$使得$|S|\geq t\cdot c (G-S)$成立,其中$c (G-S)\geq2$,则称$G$是$t$-坚韧图。满足不等式条件的最大值$t$称为图$G$的坚韧度。本文给出了如下$t$-坚韧图哈密尔顿性的一个充分条件。设$G$是一个$t$-坚韧图,$t\geq1$,$|V (G)|=n\geq 3$,若任意两个非邻接点$u,v\in V (G)$满足$\max\{d (u),d (v)\}>\frac{n}{1+t}+2t-2$,则$G$是一个哈密尔顿图。
Let $t $ be a nonnegative real number, $S$ be a subset of $V(G)$ and $c(G-S)$ denote the number of components of $G-S$. The graph $G$ is said to be $t$-tough if $|S|\geq t\cdot c(G-S)$ with $c(G-S)\geq 2$ for each vertex set $S$. The toughness is the largest real number $t$ satisfying the above condition. The following result will be proved in this paper. Let $G$ be a $t$-tough graph on $n\geq 3$ vertices with $t\geq 1$. If it holds that $\max \{d(u),d(v)\}>\frac{n}{1+t}+2t-2$ for any two nonadjacent vertices, then $G$ is Hamiltonian.
[1] Chvátal V. Tough graphs and Hamiltonian circuits [J]. Discrete Mathematics, 1973, 5: 215-218.
[2] Bauer D. Broersma H J, Veldman H J. Not every 2-tough graph is Hamiltonian [J]. Discrete Applied Mathematics, 2000, 99(1-3): 317-321.
[3] Bauer D. Broersma H J, Schmeichel E. Toughness in graphs—a survey [J]. Graphs and Combinatorics, 2006, 22(1): 1-35.
[4] Dirac G A. Some theorems on abstract graphs [J]. Proceedings of the London Mathematical Society, 1952, s3-2(1): 69-81.
[5] Fan G. New sufficient condition for cycles in graphs [J]. Journal of Combinatorial Theory, Series B, 1984, 37: 221-227.
[6] Veldman H J. Existence of Dλ-cycles and Dλ-paths [J]. Discrete Mathematics, 1983, 44(4): 309-316.
[7] Shan S. An Ore-type condition for hamiltonicity in tough graphs [J]. The Electronic Journal of Combinatorics, 2022, 29(1): P1.5.
[8] Shan S. Hamiltonian cycles in tough (P2∪ P3)-free graphs [J]. The Electronic Journal of Combinatorics, 2021, 28(1): P1.36.
北大中文核心期刊