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)\leq \kappa(G) \) of order \(n \geq 3\), then \(G\) has a Hamilton cycle,

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