kk-regular bipartite domination number bound

From papers

Let GG be a kk-regular bipartite graph with bipartition V(G)=ABV(G)=A\cup B and A=B=n|A|=|B|=n. Let γ(G)\gamma(G) be the domination number of GG, and let ρG\rho_G denote its normalised domination density. kk-regular bipartite domination number bound. For every such graph,

γ(G)2nk,ρG1nnk.\gamma(G)\leq 2\left\lceil \frac{n}{k}\right\rceil, \qquad \rho_G\leq\frac{1}{n}\left\lceil \frac{n}{k}\right\rceil.

The bound is proposed as a route toward proving Vizing's conjecture for balanced kk-regular bipartite graphs. It is not proved in full generality and is used in the paper to reduce the remaining verification to finitely many unresolved cases.

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

Noah Hosking, “Domination Density and an Imbalance Regime for Vizings Conjecture”, arXiv:2509.10473 (2026).

Solutions 0

No solutions have been posted yet.