On the sizes of bi-k-maximal graphs

Let $$k,n, s, t > 0$$k,n,s,t>0 be integers and $$n = s+t \ge 2k+2$$n=s+t≥2k+2. A simple bipartite graph G spanning $$K_{s,t}$$Ks,t is bi-k-maximal, if every subgraph of G has edge-connectivity at most k but any edge addition that does not break its bipartiteness creates a subgraph with connectivity at least $$k+1$$k+1. We investigate the optimal size bounds of the bi-k-maximal simple graphs, and prove that if G is a bi-k-maximal graph with $$\min \{s, t \} \ge k$$min{s,t}≥k on n vertices, then each of the following holds. (i)Let m be an integer. Then there exists a bi-k-maximal graph G with $$m = |E(G)|$$m=|E(G)| if and only if $$m = nk - rk^2 + (r-1)k$$m=nk-rk2+(r-1)k for some integer r with $$1\le r \le \lfloor \frac{n}{2k+2}\rfloor $$1≤r≤⌊n2k+2⌋.(ii)Every bi-k-maximal graph G on n vertices satisfies $$|E(G)| \le (n-k)k$$|E(G)|≤(n-k)k, and this upper bound is tight.(iii)Every bi-k-maximal graph G on n vertices satisfies $$|E(G)| \ge k(n-1) - (k^2-k)\lfloor \frac{n}{2k+2}\rfloor $$|E(G)|≥k(n-1)-(k2-k)⌊n2k+2⌋, and this lower bound is tight. Moreover, the bi-k-maximal graphs reaching the optimal bounds are characterized.