For a non-negative integer $sle |V(G)|-3$, a graph $G$ is $s$-Hamiltonian if the removal of any $kle s$ vertices results in a Hamiltonian graph. Given a connected 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-closed path $P$ in which all internal vertices have degree 2 such that $P$ is not both of length 2 and in a $K_3$. For a simple graph $G$, we establish better upper bounds 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 }sge 1; & 2+leftlceillgfrac{s+1}{delta(G)-2}rightrceil, && mbox{ if } 3ledelta(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 5$, this new upper bound for the $s$-hamiltonian index implies that $h_s(G) = o(ell(G)+s+1)$ as $s to infty$. This sharpens the result, $h_s(G)leell(G)+s+1$, obtained by Zhang et al. in [Discrete Math., 308 (2008) 4779-4785].
Download