The size of strength‐maximal graphs

Let G be a graph and let k ′( G ) be the edge‐connectivity of G . The strength of G , denoted by k̄′( G ), is the maximum value of k ′( H ), where H runs over all subgraphs of G . A simple graph G is called k‐ maximal if k̄′( G ) ≤ k but for any edge e ∈ E ( G c ), k̄′( G + e ) ≥ k + 1. Let G be a k ‐maximal graph of order n . In [3], Mader proved | E ( G )| ≤ ( n ‐ k ) k + (   2 k ). In this note, we shall show ( n ‐ 1) k ‐ (   2 k ) In⌊ n / k + 2)⌋ ≤ | E ( G |, and characterize the extremal graphs. We shall also give a characterization of all k ‐maximal graphs.