关键词: 坚韧度, 哈密尔顿图, 非邻接点

Abstract: 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.

Key words: toughness, Hamiltonian, nonadjacent vertices