The bipartite unique domination bound

From papers

Let G=(V,E)G=(V,E) be a finite simple bipartite graph without isolated vertices, with order n=Vn=|V| and domination number γ(G)=γ\gamma(G)=\gamma. A unique minimum dominating set is a minimum dominating set of GG that is the only one. Define

Φ(n,γ)=max(0,n3γ2γ2γ2+1).\Phi(n,\gamma)=\max\left(0,n-3\gamma-2\left\lceil\frac{\gamma}{2}\right\rceil-\left\lfloor\frac{\gamma}{2}\right\rfloor+1\right).

Bipartite unique domination bound. If GG has a unique minimum dominating set, γ2\gamma\geq 2, and n3γn\geq 3\gamma, then its size s(G)s(G) is bounded above by

m(n,\gamma)=2\gamma+2\left\lceil\frac{\gamma}{2}\right\rceil\left\lfloor\frac{\gamma}{2}\right\rfloor+\min\left\\{n-3\gamma,2\left\lceil\frac{\gamma}{2}\right\rceil-\left\lfloor\frac{\gamma}{2}\right\rfloor+1\right\\}\left(2\left\lceil\frac{\gamma}{2}\right\rceil+1\right)+\sum_{i=1}^{\Phi}\left(2\left\lceil\frac{\gamma}{2}\right\rceil+1+\left\lceil\frac{i}{2}\right\rceil\right).

This conjecture proposes the sharp edge bound for bipartite graphs with a unique minimum dominating set in the stated range, refining the general bounds for uniquely dominatable graphs and complementing known results for special cases such as domination number 22.

Progress summary

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

Sources & referencesView supporting material

Primary source

Garrison Koch and Darren Narayan, “Maximal bipartite graphs with a unique minimum dominating set”, arXiv:2511.01719 (2025).

Solutions 0

No solutions have been posted yet.