In [3], Faudree and Gould showed that if a 2-connected graph contains no and P₆ as an induced subgraph, then the graph is hamiltonian. In this paper, we consider the extension of this result to cycles passing through specified vertices. We define the families of graphs which are extension of the forbidden pair and P₆, and prove that the forbidden families implies the existence of cycles passing through specified vertices.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1470,
author = {Takeshi Sugiyama and Masao Tsugaki},
title = {Pairs of forbidden class of subgraphs concerning $K\_{1,3}$ and P6 to have a cycle containing specified vertices},
journal = {Discussiones Mathematicae Graph Theory},
volume = {29},
year = {2009},
pages = {645-650},
zbl = {1194.05063},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1470}
}
Takeshi Sugiyama; Masao Tsugaki. Pairs of forbidden class of subgraphs concerning $K_{1,3}$ and P₆ to have a cycle containing specified vertices. Discussiones Mathematicae Graph Theory, Tome 29 (2009) pp. 645-650. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1470/
[000] [1] H. Broersma, H. Li, J. Li, F. Tian and H.J. Veldman, Cycles through subsets with large degree sums, Discrete Math. 171 (1997) 43-54, doi: 10.1016/S0012-365X(96)00071-4. | Zbl 0883.05089
[001] [2] R. Diestel, Graph Theory, second edition (New York, Springer, 2000).
[002] [3] R. Faudree and R. Gould, Characterizing forbidden pairs for hamiltonian properties, Discrete Math. 173 (1997) 45-60, doi: 10.1016/S0012-365X(96)00147-1. | Zbl 0879.05050
[003] [4] J. Fujisawa, K. Ota, T. Sugiyama and M. Tsugaki, Forbidden subgraphs and existence of paths and cycles passing through specified vertices, Discrete Math. 308 (2008) 6111-6114, doi: 10.1016/j.disc.2007.11.033. | Zbl 1158.05036
[004] [5] K. Ota, Cycles through prescribed vertices with large degree sum, Discrete Math. 145 (1995) 201-210, doi: 10.1016/0012-365X(94)00036-I. | Zbl 0838.05071
[005] [6] T. Sugiyama, Forbidden subgraphs and existence of cycles passing through specified vertices, in preparation. | Zbl 1158.05036