Minimum order of an extremal bipartite graph

About 7 years old · traced to

Let a(G)a(G) be the annihilation number, α(G)\alpha(G) the independence number, and μ(G)\mu(G) the matching number of a bipartite graph GG. The graph is called extremal when equality holds in the bipartite bound

a(G)−α(G)=2+μ(G)−21+μ(G).a(G)-\alpha(G)=2+\mu(G)-2\sqrt{1+\mu(G)}.

Minimum-order conjecture. The minimum number of vertices of an extremal bipartite graph is 1616.

The claim identifies the smallest order at which equality in the paper's sharp bipartite inequality can occur. Its resolution is not indicated in the supplied material, so it remains open in this record.

References

Primary source

Ohr Kadrawi and Vadim E. Levit, “Inequalities Connecting the Annihilation and Independence Numbers”, arXiv:2308.01685 (2023).

Additional references

2 papers in this index state this conjecture (2019–2023). The statement above is taken from the most recent of them; the others are arXiv:1902.10344.

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.