Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903607 | European Journal of Combinatorics | 2018 | 20 Pages |
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
Shinya Fujita, Henry Liu, Amites Sarkar,