The main conjecture on degree-\a0k+1k+1 vertices in minimal kk-extendable bipartite graphs

About 2 years old · traced to

Let GG be a minimal kk-extendable bipartite graph, with k⩾1k\geqslant 1, order nn, and size m=∣E(G)∣m=|E(G)|. Let Vk+1V_{k+1} be the set of vertices of degree precisely k+1k+1. Main conjecture.

∣Vk+1∣⩾22k−1(m−n+2k).|V_{k+1}|\geqslant \frac{2}{2k-1}(m-n+2k).

This conjecture is proposed as a strengthening of Lou's lower bound in terms of the order and size; its status is not resolved in the supplied text.

References

Primary source

Amit Kumar Mallik, Ajit A. Diwan and Nishad Kothari, “Extremal minimal bipartite matching covered graphs”, arXiv:2404.06445 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.