On Generalizing a Theorem of Jung

Abstract

For a graph $G$, let ${\sigma }_k=min\{\sum _{i=1}^{k}d(v_i)\mid \{v_1,\dots ,v_k\}$ { is an independent set
of vertices in } G\}. Jung proved that every $1$-tough graph $G$ with $|V(G)|=n\ge 11$ and ${\sigma }_2>n-4$ is hamiltonian. This result is generalized as follows: if $G$ is a $1$-tough graph with $|V(G)|=n\ge 3$ such that ${\sigma }_3>n$ and for all $x,y\in V(G)$, $d(x,y)=2$ implies $max\{d(x),d(y)\}\ge \frac{1}{2}(n-4)$, then $G$ is hamiltonian. It is also shown that the condition ${\sigma }_3\ge n$, in the latter result, can be dropped if $G$ is required to be $3$-connected and to have at least $35$ vertices.