Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651078 | Discrete Mathematics | 2007 | 4 Pages |
Abstract
Let GG be a graph and SS a subset of V(G)V(G). Let α(S)α(S) denote the maximum number of pairwise nonadjacent vertices in the subgraph G〈S〉G〈S〉 of GG induced by SS. If G〈S〉G〈S〉 is not complete, let κ(S)κ(S) denote the smallest number of vertices separating two vertices of SS and κ(S)=|S|-1κ(S)=|S|-1 otherwise. We prove that if α(S)⩽κ(S)α(S)⩽κ(S) and |S||S| is large enough (depending on α(S)α(S)), then GG is SS-pancyclable, that is contains cycles with exactly pp vertices of SS for every pp, 3⩽p⩽|S|3⩽p⩽|S|.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Evelyne Flandrin, Hao Li, Antoni Marczyk, Mariusz Woźniak,