| Affiliation: | a L.R.I., Bat. 490, Université de Paris-Sud, 91405 Orsay Cedex, France
b Department of Mathematics, University of Mississippi, University, MS 38677, United States
c Institute of Systems Science, Academy of Mathematics and System Sciences, Chinese Academy of Sciences, Beijing 100080, China |
| Abstract: | Let G be a graph of order n and S be a vertex set of q vertices. We call G,S-pancyclable, if for every integer i with 3≤i≤q there exists a cycle C in G such that |V(C)∩S|=i. For any two nonadjacent vertices u,v of S, we say that u,v are of distance two in S, denoted by dS(u,v)=2, if there is a path P in G connecting u and v such that |V(P)∩S|≤3. In this paper, we will prove that if G is 2-connected and for all pairs of vertices u,v of S with dS(u,v)=2,  , then there is a cycle in G containing all the vertices of S. Furthermore, if for all pairs of vertices u,v of S with dS(u,v)=2,  , then G is S-pancyclable unless the subgraph induced by S is in a class of special graphs. This generalizes a result of Fan [G. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory B 37 (1984) 221-227] for the case when S=V(G). |
