Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651148 | Discrete Mathematics | 2007 | 7 Pages |
Abstract
Let X be a subset of the vertex set of a graph G . We denote by κ(X)κ(X) the smallest number of vertices separating two vertices of X if X does not induce a complete subgraph of G , otherwise we put κ(X)=|X|-1κ(X)=|X|-1 if |X|⩾2|X|⩾2 and κ(X)=1κ(X)=1 if |X|=1|X|=1. We prove that if κ(X)⩾2κ(X)⩾2 then every set of at most κ(X)κ(X) vertices of X is contained in a cycle of G. Thus, we generalize a similar result of Dirac. Applying this theorem we improve our previous result involving an Ore-type condition and give another proof of a slightly improved version of a theorem of Broersma et al.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Evelyne Flandrin, Hao Li, Antoni Marczyk, Mariusz Woźniak,