Article ID Journal Published Year Pages File Type
8903607 European Journal of Combinatorics 2018 20 Pages PDF
Abstract
Let G be a graph on n vertices with independence number α. We prove that if n is sufficiently large (n≥α2k+1 will do), then G always contains a k-connected subgraph on at least n∕α vertices. The value of n∕α is sharp, since G might be the disjoint union of α equally-sized cliques. For k≥3 and α=2,3, we shall prove that the same result holds for n≥4(k−1) and n≥27(k−1)4 respectively, and that these lower bounds on n are sharp.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,