On the number of edges in a graph with no $(k+1)$-connected subgraphs

Abstract

Mader proved that for $k\ge 2$ and $n\ge 2k$, every $n$-vertex graph with no $(k+1)$-connected subgraphs has at most $(1+\frac{1}{\sqrt{2}})k(n-k)$ edges. He also conjectured that for $n$ large with respect to $k$, every such graph has at most $\frac{3}{2}\left(k-\frac{1}{3}\right)(n-k)$ edges. Yuster improved Mader's upper bound to $\frac{193}{120}k(n-k)$ for $n\ge \frac{9k}{4}$. In this note, we make the next step towards Mader's Conjecture: we improve Yuster's bound to $\frac{19}{12}k(n-k)$ for $n\ge \frac{5k}{2}$.

8 pages; a few typos have been fixed

Cited by in corpus (4)

• Finding Densest $k$-Connected Subgraphs
• Large highly connected subgraphs in graphs with linear average degree
• Structural properties of bipartite subgraphs
• On the sizes of vertex-$k$-maximal $r$-uniform hypergraphs