Article
Highly Connected Subgraphs of Graphs with Given Independence Number (Extended Abstract)
Electronic Notes in Discrete Mathematics
(2016)
Abstract
Let G be a graph on n vertices with independence number α. What is the largest k-connected subgraph that G must contain? We prove that if n is sufficiently large (n≥α2k+1 will do), then G contains a k-connected subgraph on at least n/α vertices. This 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 sharp.
Keywords
- Connectivity,
- Highly connected subgraph,
- Independence number
Disciplines
Publication Date
January 10, 2016
DOI
10.1016/j.endm.2016.09.019
Citation Information
Shinya Fujita, Henry Liu and Amites Sarkar. "Highly Connected Subgraphs of Graphs with Given Independence Number (Extended Abstract)" Electronic Notes in Discrete Mathematics Vol. 54 (2016) p. 103 - 108 Available at: http://works.bepress.com/amites_sarkar/19/