{"id":"arxiv/2607.25188","url":"https://arxiv.org/abs/2607.25188","tags":["math.CO"],"score":0,"title":"Nordhaus-Gaddum Inequalities for Dominating-Set Counts in Bipartite Graphs","domain":"math.CO","source":"arxiv","authors":["T. N. Sanh"],"reviews":0,"subject":"math.CO","summary":"A dominating set in a graph $G$ is a subset $S$ of its vertices such that each vertex in $G$ is either in $S$ or adjacent to a vertex in $S$. Nordhaus-Gaddum inequalities relate the values of a graph parameter on a graph and its complement. In this setting, Keough and Shane conjecture that any graph $G$ on $n$ vertices satisfies $\\partial(G) + \\partial(\\bar{G}) \\leq 2(2^{\\lfloor n/2 \\rfloor} - 1)(2^{\\lceil n/2 \\rceil} - 1) + 2$, where $\\partial(G)$ is the number of dominating sets in $G$. We partially resolve this conjecture for the bipartite case by proving the stronger bound: for a…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-28","reactions":{}}