The bipartite unique domination bound
The bipartite unique domination bound
Let be a finite simple bipartite graph without isolated vertices, with order and domination number . A unique minimum dominating set is a minimum dominating set of that is the only one. Define
Bipartite unique domination bound. If has a unique minimum dominating set, , and , then its size 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 .
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
Sign in to submit a solution.
No solutions have been posted yet.