s -Vertex Pancyclic Index

A graph G is vertex pancyclic if for each vertex $${v \in V(G)}$$, and for each integer k with 3 ≤ k ≤ |V(G)|, G has a k-cycle C k such that $${v \in V(C_k)}$$. Let s ≥ 0 be an integer. If the removal of at most s vertices in G results in a vertex pancyclic graph, we say G is an s-vertex pancyclic graph. Let G be a simple connected graph that is not a path, cycle or K 1,3. Let l(G) = max{m : G has a divalent path of length m that is not both of length 2 and in a K 3}, where a divalent path in G is a path whose interval vertices have degree two in G. The s-vertex pancyclic index of G, written vp s (G), is the least nonnegative integer m such that L m (G) is s-vertex pancyclic. We show that for a given integer s ≥ 0, $$vp_s(G)\le \left\{\begin{array}{[email protected]{\quad}l} \qquad\quad\quad\,\,\,\,\,\,\, l(G)+s+1: \quad {\rm if} \,\, 0 \le s \le 4 \\ l(G)+\lceil {\rm log}_2(s-2) \rceil+4: \quad {\rm if} \,\, s \ge 5 \end{array}\right.$$ And we improve the bound for essentially 3-edge-connected graphs. The lower bound and whether the upper bound is sharp are also discussed.