Abstract
Let \(k\le m\le n\) be fixed positive integers. A graph of order \(n\) is \((k,m)\)-pancyclic if for any set of \(k\) vertices and any integer \(r\) with \(m\le r\le n\), there is a cycle of length \(r\) containing the \(k\) vertices. If the additional property that the \(k\) vertices must appear on the cycle in a specified order is required, then the graph is said to be \((k,m)\)-pancyclic ordered. Faudree et al. (Graphs Comb 20:291–309, 2004) gave the condition of the minimum sum of degree of two nonadjacent vertices that implies a graph to be \((k,m)\)-pancyclic or \((k,m)\)-pancyclic ordered. In this paper, we introduce a stronger related property, \((k,m)\)-vertex-pancyclic ordered graphs, which requires for any specified vertex \(v\) and any ordered set \(S\) of \(k\) vertices there is a cycle of length \(r\) containing \(v\) and \(S\) and encountering the vertices of \(S\) in the specified order for each \(m\le r\le n\). The condition of the minimum sum of degree of two nonadjacent vertices that implies a graph is \((k,m+2)\)-vertex-pancyclic ordered are presented. Examples introduced by Faudree et al. also show that these constraints are best possible.

Similar content being viewed by others
References
Bollobás, B.: Extremal Graph Theory. Academic Press, London (1978)
Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. The Macmillan Press Ltd, London (1976)
Chartrand, G., Lesniak, L.: Graphs and Digraphs. Chapman and Hall, London (1996)
Faudree, R.J.: Survey of results on \(k\)-ordered graphs. Discrete Math. 229(1–3), 73–87 (2001)
Faudree, R.J., Gould, R.J., Kostochka, A.V., Lesniak, L., Schiermeyer, I., Saito, A.: Degree conditions for \(k\)-ordered hamiltonian graphs. J. Graph Theory 42(3), 199–210 (2003)
Faudree, R.J., Gould, R.J., Jacobson, M.S., Lesniak, L.: Generalizing pancyclic and \(k\)-ordered graphs. Graphs Comb. 20(3), 291–309 (2004)
Li, R.: A Fan-type result on \(k\)-ordered graphs. Inf. Process. Lett. 110(16), 651–654 (2010)
Li, R., Li, S., Guo, Y.: Degree conditions on distance 2 vertices that imply \(k\)-ordered Hamiltonian. Discrete Appl. Math. 158(4), 331–339 (2010)
Mészáros, K.: On low degree \(k\)-ordered graphs. Discrete Math. 308(12), 2149–2155 (2008)
Ng, L., Schultz, M.: \(k\)-ordered Hamiltonian graphs. J. Graph Theory 24(1), 45–57 (1997)
Acknowledgments
We express our sincere thanks to the referees for their valuable suggestions and detailed comments.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is supported partially by the Youth Foundation of Shanxi Province (2013021001-5) and Shanxi Scholarship Council of China (2013-017) and NNSFC under no. 11201273.
Rights and permissions
About this article
Cite this article
Li, R., Zhang, X. & Guo, Q. Generalizing Vertex Pancyclic and \(k\)-ordered Graphs. Graphs and Combinatorics 31, 1539–1554 (2015). https://doi.org/10.1007/s00373-014-1460-y
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-014-1460-y