zbMATH — the first resource for mathematics

\(s\)-vertex pancyclic index. (English) Zbl 1256.05125
Summary: A graph \(G\) is vertex pancyclic if for each vertex \(v \in V(G)\), and for each integer \(k\) with \(3 \leq k \leq |V(G)|\), \(G\) has a \(k\)-cycle \(C_{k}\) such that \(v \in V(C_k)\). Let \(s \geq 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 \geq 0\),
\[ vp_s(G) \leq \begin{cases} l(G)+s+1: \quad &\text{if }0 \leq s \leq 4 \\ l(G)+\lceil {\log}_2(s-2) \rceil+4: \quad &\text{if }s \geq 5 \end{cases}. \] And we improve the bound for essentially 3-edge-connected graphs. The lower bound and whether the upper bound is sharp are also discussed.

05C38 Paths and cycles
05C76 Graph operations (line graphs, products, etc.)
Full Text: DOI
[1] Bondy J.A., Murty U.S.R.: Graph Theory with Applications. American Elsevier, New York (1976) · Zbl 1226.05083
[2] Broersma H.J., Veldman H.J.: 3-connected line graphs of triangular graphs are panconnected and 1-hamiltonian. J. Graph Theory 11, 399–407 (1987) · Zbl 0656.05045 · doi:10.1002/jgt.3190110314
[3] Chartrand G., Wall C.E.: On the Hamiltonian index of a graph. Stud. Sci. Math. Hung 8, 38–43 (1973) · Zbl 0279.05121
[4] Clark L.H., Wormald N.C.: Hamiltonian-like indices of the graphs. Ars Combin. 15, 131–148 (1983) · Zbl 0536.05046
[5] Harary F., Nash-Williams C.St.J.A.: On Eulerian and Hamiltonian graphs and line graphs. Can. Math. Bull 9, 701–710 (1965) · Zbl 0136.44704 · doi:10.4153/CMB-1965-051-3
[6] Hartke S., Higgins A.: Minimum degree growth of the iterated line graph. Ars Combin. 69, 275–283 (2003) · Zbl 1072.05566
[7] Knor M., Niepel L’.: Connectivity of iterated line graphs. Discret. Appl. Math. 125, 255–266 (2003) · Zbl 1009.05086 · doi:10.1016/S0166-218X(02)00197-X
[8] Lai H.-J.: On the Hamiltonian index. Discret. Math. 69, 43–53 (1988) · Zbl 0638.05034 · doi:10.1016/0012-365X(88)90176-8
[9] Zhang L., Eschen E., Lai H.-J., Shao Y.: The s-Hamiltonian index. Discret Math. 308, 4779–4785 (2008) · Zbl 1223.05166 · doi:10.1016/j.disc.2007.08.073
[10] Shao Y.: Connectivity of iterated line graphs. Discret. Appl. Math. 158, 2081–2087 (2010) · Zbl 1215.05097 · doi:10.1016/j.dam.2010.08.024
[11] West D.: Introduction to Graph Theory. Prentice Hall, New Jersey (2001) · Zbl 0992.83079
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.