Title

Asymptotically sharpening the s-Hamiltonian index bound

Document Type

Article

Publication Date

1-1-2022

Abstract

For a non-negative integer s ≤ |V (G)| − 3, a graph G is s-Hamiltonian if the removal of any k ≤ s vertices results in a Hamiltonian graph. Given a connected simple graph G that is not isomorphic to a path, a cycle, or a K1,3, let δ(G) denote the minimum degree of G, let hs(G) denote the smallest integer i such that the iterated line graph Li(G) is s-Hamiltonian, and let ℓ(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 K3. For a simple graph G, we establish better upper bounds for hs(G) as follows. if δ(G) ≤ 2 and s = 0; hs(G) ≤ 2 2ℓ de ( (+G G ) ) + + lg1 2 δ(+ s G + ⌈ ) lg(− 1 s 2 + , 1)⌉, if δ(G) ≤ 2 and s ≥ 1; if 3 ≤ δ(G) ≤ s + 2; otherwise, where de(G) is the smallest integer i such that δ(Li(G)) ≥ 3. Consequently, when s ≥ 6, this new upper bound for the s-hamiltonian index implies that hs(G) = o(ℓ(G) + s + 1) as s → ∞. This sharpens the result, hs(G) ≤ ℓ(G) + s + 1, obtained by Zhang et al. in [Discrete Math., 308 (2008) 4779-4785].

Link to Full Text
COinS