Discussiones Mathematicae Graph Theory 29(3) (2009) 645-650
doi: 10.7151/dmgt.1470

[BIBTex] [PDF] [PS]

PAIRS OF FORBIDDEN CLASS OF SUBGRAPHS CONCERNING K1,3 AND P6 TO HAVE A CYCLE CONTAINING SPECIFIED VERTICES

Takeshi Sugiyama

Department of Mathematics, Keio University
Hiyoshi, Kohoku-ku, Yokohama, 223-8522, Japan
e-mail: sugiyama@comb.math.keio.ac.jp

Masao Tsugaki

Department of Mathematical Information Science
Tokyo University of Science
1-3 Kagurazaka, Shinjuku-ku, Tokyo 162-8601, Japan
e-mail: tsugaki@hotmail.com

Abstract

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

Keywords: forbidden subgraph, cycle.

2000 Mathematics Subject Classification: 05C38.

References

[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.

Received 4 February 2008
Revised 2 January 2009
Accepted 10 March 2009