The Hamiltonicity of $k$-Connected $[s,t]$-Graphs

Abstract

A graph $G$ is an {$[s,t]$-graph if every subgraph induced by $s$ vertices of $G$ has at least $t$ edges. This concept extends the independent number. In this paper, we prove that:

(1) if $G$ is a $k$-connected $[k+2,2]$-graph, then $G$ has a Hamilton cycle or $G$ is isomorphic to the Petersen graph or $\overline{K_{k+1}}\vee G_k$,

(2) if $G$ is a $k$-connected $[k+3,2]$-graph, then $G$ has a Hamilton path or $G$ is isomorphic to $\overline{K_{k+1}}\vee G_k$,
where $G_r$ is an arbitrary graph of order $k$. These two results generalize the following known results obtained by Chvátal-Erdős and Bondy, respectively:

(a) if $\alpha (G)\le \kappa (G)$ of order $n\ge 3$, then $G$ has a Hamilton cycle,

(b) if $\alpha (G)–1\le \kappa (G)$ , then $G$ has a Hamilton path.