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

Abstract: Mader proved that for

k g e q 2

and

n g e q 2 k

, every

n

-vertex graph with no

(k + 1)

-connected subgraphs has at most

(1 + f r a c 1 s q r t 2) k (n - k)

edges. He also conjectured that for

n

large with respect to

k

, every such graph has at most

f r a c 32 l e f t (k - f r a c 13 i g h t) (n - k)

edges. Yuster improved Mader's upper bound to

f r a c 193120 k (n - k)

for

n g e q f r a c 9 k 4

. In this note, we make the next step towards Mader's Conjecture: we improve Yuster's bound to

f r a c 1912 k (n - k)

for

n g e q f r a c 5 k 2

.

Recommendations

Cites work

Cited in

(15)

This page was built for publication: On the number of edges in a graph with no \((k + 1)\)-connected subgraphs