On the sizes of bi-\(k\)-maximal graphs (Q2307504)

Let \(k,n,s,t>0\) be integers, and let \(S\), \(T\) be sets of size \(s\), \(t\) respectively. For an integer \(k\le\frac{n}{2}-1\) (where \(n=s+t\)) a bipartite graph \(G=G(S,T,E)\) with vertex parts \(S\), \(T\) is called bi-\(k\)-maximal if every subgraph of \(G\) has edge connectivity at most \(k\), but the addition of any new \(S-T\) edge creates a graph of edge connectivity at least \(k+1\). In this paper under review, the authors prove the following two results. Suppose \(k\le \min\{s,t\}\). \par i) There exists a bi-\(k\)-maximal graph \(G=G(S,T,E)\) with \(m\) edges if and only if \(m=nk-rk^2+(r-1)k\) for some integer \(r\in[1,\lfloor\frac{n}{2k+2}\rfloor\). \par ii) If \(G\) is bi-\(k\)-maximal then \(e(G)\ge k(n-1)-(k^2-k)\lfloor\frac{n}{2k+2}\rfloor\), and this bound is tight. In addition, the authors also give a structural characterization of the extremal bi-\(k\)-maximal graphs in these cases.