Operations Research Transactions ›› 2026, Vol. 30 ›› Issue (2): 225-231.doi: 10.15960/j.cnki.issn.1007-6093.2026.02.017

Previous Articles     Next Articles

A sufficient condition for hamiltonicity in t-tough graphs

CHEN Tao   

  1. Department of Basic Courses, Nanjing Tech University Pujiang Institute, Nanjing 211200, Jiangsu, China
  • Received:2023-05-10 Published:2026-06-12

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

CLC Number: