Lower bound on the minus-domination number Original Research Article

For a graph G, a function f :V(G)→{−1,0,+1} is called a minus-dominating function of G if the closed neighborhood of each vertex of G contains strictly more 1ʹs than −1ʹs. The minus-domination number γ−(G) of G, as defined by Henning and Slater, is the minimum, over all minus-dominating functions f of G, of ∑v∈V(G) f(v). As observed by Füredi and Mubayi, a well-known probabilistic bound for the size of a transversal of a set system implies that γ−(G)=O((n/r) log r) for any graph G on n vertices of minimum degree r. We prove that there exist r-regular multigraphs G on n vertices, in which each vertex has at least r/2 distinct neighbors, and such that γ−(G)⩾c(n/r) log r for some constant c>0. (For a multigraph, the closed neighborhood of a vertex is considered as a multiset in the definition of a minus-dominating function.)