{"docId":9649,"paperId":8484,"url":"https:\/\/dmtcs.episciences.org\/8484","doi":"10.46298\/dmtcs.8484","journalName":"Discrete Mathematics & Theoretical Computer Science","issn":"","eissn":"1365-8050","volume":[{"vid":608,"name":"vol. 24, no. 1"}],"section":[{"sid":9,"title":"Graph Theory","description":[]}],"repositoryName":"arXiv","repositoryIdentifier":"2109.05660","repositoryVersion":3,"repositoryLink":"https:\/\/arxiv.org\/abs\/2109.05660v3","dateSubmitted":"2021-09-15 18:47:40","dateAccepted":"2022-05-24 14:15:17","datePublished":"2022-06-13 15:34:01","titles":["Asymptotically sharpening the $s$-Hamiltonian index bound"],"authors":["Song, Sulin","Lei, Lan","Shao, Yehong","Lai, Hong-Jian"],"abstracts":["For a non-negative integer $s\\le |V(G)|-3$, a graph $G$ is $s$-Hamiltonian if the removal of any $k\\le 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 }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 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)\\le\\ell(G)+s+1$, obtained by Zhang et al. in [Discrete Math., 308 (2008) 4779-4785].","Comment: 9 pages"],"keywords":["Mathematics - Combinatorics","05C40, 05C45, 05C76","G.2.2"]}