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