Asymptotically sharpening the $s$-Hamiltonian index bound

For a non-negative integer $s\le |V(G)|-3$, a graph $G$ is $s$-Hamiltonian ifthe removal of any $k\le s$ vertices results in a Hamiltonian graph. Given aconnected simple graph $G$ that is not isomorphic to a path, a cycle, or a$K_{1,3}$, let $\delta(G)$ denote the minimum degree of $G$, let $h_s(G)$denote the smallest integer $i$ such that the iterated line graph $L^{i}(G)$ is$s$-Hamiltonian, and let $\ell(G)$ denote the length of the longest non-closedpath $P$ in which all internal vertices have degree 2 such that $P$ is not bothof length 2 and in a $K_3$. For a simple graph $G$, we establish better upperbounds for $h_s(G)$ as follows. \begin{equation*} h_s(G)\le \left\{\begin{aligned} & \ell(G)+1, &&\mbox{ if }\delta(G)\le 2 \mbox{ and }s=0;\\ &\widetilde d(G)+2+\lceil \lg (s+1)\rceil, &&\mbox{ if }\delta(G)\le 2 \mbox{and }s\ge 1;\\ & 2+\left\lceil\lg\frac{s+1}{\delta(G)-2}\right\rceil, && \mbox{if } 3\le\delta(G)\le s+2;\\ & 2, &&{\rm otherwise}, \end{aligned} \right.\end{equation*} where $\widetilde d(G)$ is the smallest integer $i$ such that$\delta(L^i(G))\ge 3$. Consequently, when $s \ge 6$, this new upper bound forthe $s$-hamiltonian index implies that $h_s(G) = o(\ell(G)+s+1)$ as $s \to\infty$. This sharpens the result, $h_s(G)\le\ell(G)+s+1$, obtained by Zhang etal. in [Discrete Math., 308 (2008) 4779-4785].Comment: 9 page