language-icon Old Web
English
Sign In

On the sizes of bi-k-maximal graphs

2020 
Let $$k,n, s, t > 0$$ be integers and $$n = s+t \ge 2k+2$$. A simple bipartite graph G spanning $$K_{s,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$$. 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$$ on n vertices, then each of the following holds.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    13
    References
    0
    Citations
    NaN
    KQI
    []