
arXiv: 2109.05660
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].
05C40, 05C45, 05C76, Eulerian and Hamiltonian graphs, \(k\)-triangular graph, mathematics - combinatorics, \((s, t)\)-supereulerian, g.2.2, line graph stable properties, G.2.2, collapsible graphs, \(s\)-Hamiltonian, 05c40, 05c45, 05c76, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics
05C40, 05C45, 05C76, Eulerian and Hamiltonian graphs, \(k\)-triangular graph, mathematics - combinatorics, \((s, t)\)-supereulerian, g.2.2, line graph stable properties, G.2.2, collapsible graphs, \(s\)-Hamiltonian, 05c40, 05c45, 05c76, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
