Article ID Journal Published Year Pages File Type
4651148 Discrete Mathematics 2007 7 Pages PDF
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
, , , ,