Pairs of forbidden class of subgraphs concerning $K_{1,3}$ and P₆ to have a cycle containing specified vertices

• Autorzy: Takeshi Sugiyama , Masao Tsugaki
• Języki publikacji: EN

Abstrakty

EN

In [3], Faudree and Gould showed that if a 2-connected graph contains no $K_{1,3}$ 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 $K_{1,3}$ and P₆, and prove that the forbidden families implies the existence of cycles passing through specified vertices.

Słowa kluczowe

EN

forbidden subgraph; cycle

Kategorie tematyczne

• 05C38: Paths and cycles

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2009
• Tom: 29
• Numer: 3
• Strony: 645-650

Daty

wydano

2009

otrzymano

2008-02-04

poprawiono

2009-01-02

zaakceptowano

2009-03-10

Twórcy

autor

Takeshi Sugiyama

• Department of Mathematics, Keio University, Hiyoshi, Kohoku-ku, Yokohama, 223-8522, Japan

autor

Masao Tsugaki

• Department of Mathematical Information Science, Tokyo University of Science, 1-3 Kagurazaka, Shinjuku-ku, Tokyo 162-8601, Japan

Bibliografia

• [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.
• [2] R. Diestel, Graph Theory, second edition (New York, Springer, 2000).
• [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.
• [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.
• [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.
• [6] T. Sugiyama, Forbidden subgraphs and existence of cycles passing through specified vertices, in preparation.

Identyfikatory

DOI

10.7151/dmgt.1470