The size of strength‐maximal graphs
Hong‐Jian Lai · Journal of Graph Theory · 1990
Abstract 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(Gc), k̄′(G + e) ≥ k + 1. Let G be a k‐maximal graph of order n. In [3], Mader proved |E(G)| ≤ (n ‐ k)k + ( ). In this note, we shall show (n ‐ 1)k ‐ ( ) In⌊n/k + 2)⌋ ≤ |E(G|, and characterize the extremal graphs. We shall also give a characterization of all k‐maximal graphs.