Geodesic
Forbidden Pairs and (k, m)-Pancyclicity
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 649-663.

Voir la notice de l'article provenant de la source Library of Science

A graph G on n vertices is said to be (k,m)-pancyclic if every set of k vertices in G is contained in a cycle of length r for each r ∈ m, m+1, . . ., n. This property, which generalizes the notion of a vertex pancyclic graph, was defined by Faudree, Gould, Jacobson, and Lesniak in 2004. The notion of (k, m)-pancyclicity provides one way to measure the prevalence of cycles in a graph. We consider pairs of subgraphs that, when forbidden, guarantee hamiltonicity for 2-connected graphs on n ≥ 10 vertices. There are exactly ten such pairs. For each integer k ≥ 1 and each of eight such subgraph pairs R, S, we determine the smallest value m such that any 2-connected R, S-free graph on n ≥ 10 vertices is guaranteed to be (k,m)-pancyclic. Examples are provided that show the given values are best possible. Each such example we provide represents an infinite family of graphs.
Keywords: hamiltonian, pancyclic, forbidden subgraph, cycle, claw-free 
@article{DMGT_2017_37_3_a11,
     author = {Crane, Charles Brian},
     title = {Forbidden {Pairs} and (k, {m)-Pancyclicity}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {649--663},
     publisher = {mathdoc},
     volume = {37},
     number = {3},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a11/}
}
TY  - JOUR
AU  - Crane, Charles Brian
TI  - Forbidden Pairs and (k, m)-Pancyclicity
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 649
EP  - 663
VL  - 37
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a11/
LA  - en
ID  - DMGT_2017_37_3_a11
ER  - 
%0 Journal Article
%A Crane, Charles Brian
%T Forbidden Pairs and (k, m)-Pancyclicity
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 649-663
%V 37
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a11/
%G en
%F DMGT_2017_37_3_a11
Crane, Charles Brian. Forbidden Pairs and (k, m)-Pancyclicity. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 3, pp. 649-663. http://geodesic.mathdoc.fr/item/DMGT_2017_37_3_a11/

[1] P. Bedrossian, Forbidden subgraph and minimum degree conditions for Hamiltonicity (Ph.D. Thesis, Memphis State University, 1991).

[2] J.A. Bondy, Pancyclic graphs, in: Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory, and Computing, Ray C. Mullin (Ed(s)), (Louisiana State University, Baton Rouge, LA, 1971) 167–172. doi:10.1016/0095-8956(71)90016-5

[3] J.A. Bondy, Pancyclic graphs I, J. Combin. Theory Ser. B 11 (1971) 80–84. doi:10.1016/0095-8956(71)90016-5

[4] G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs, 5 th Edition (Chapman and Hall/CRC, Boca Raton, FL, 2011).

[5] C.B. Crane, Generalized pancyclic properties in claw-free graphs, Graphs Combin. 31 (2015) 2149–2158. doi:10.1007/s00373-014-1510-5

[6] Y. Egawa, J. Fujisawa, S. Fujita and K. Ota, On 2 -factors in r-connected { K1,k, P4} -free graphs, Tokyo J. Math. 31 (2008) 415–420. doi:10.3836/tjm/1233844061

[7] R.J. Faudree and R.J. Gould, Characterizing forbidden pairs for Hamiltonian properties, Discrete Math. 173 (1997) 45–60. doi:10.1016/S0012-365X(96)00147-1

[8] R.J. Faudree, R.J. Gould, M.S. Jacobson and L. Lesniak, Generalizing pancyclic and k-ordered graphs, Graphs Combin. 20 (2004) 291–310. doi:10.1007/s00373-004-0576-x

[9] O. Ore, Note on hamilton circuits, Amer. Math. Monthly 67 (1960) 55. doi:10.2307/2308928