2026/07/28 by T. N. Sanh
Mathematics · #math.CO
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 ∂(G) + ∂(G) ≤ 2(2\lfloor n/2 \rfloor - 1)(2\lceil n/2 \rceil - 1) + 2, where ∂(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 bipartite graph G with nonempty bipartition (A,B), it holds that ∂(G) + ∂(G) ≤ 2(2|A| - 1)(2|B| - 1) + 2. We also characterize the bipartite graphs for which equality holds.