Large highly connected subgraphs in graphs with linear average degree
classification
🧮 math.CO
keywords
averageboundconnecteddegreeconstanteveryfracgraph
read the original abstract
In 1972 Mader proved that every graph with average degree at least $4k$ has a $(k+1)$-connected subgraph with more than $2k$ vertices. We improve this bound by showing that the constant $4$ can be replaced by $3+\frac{1}{3}$; this bound is sharp.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Hypergraphs without Subgraphs of Given Connectivity
The extremal number of edges in n-vertex r-uniform hypergraphs without a (k+1)-connected subgraph is determined asymptotically for r ≥ 3, with tight bounds when connected components are bounded by Ck vertices.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.