Lower bound on the minus-domination number (Q5936043): Difference between revisions

The minus-domination number of a graph was introduced by M. A. Henning and P. J. Slater. Here the definition is modified for multigraphs instead of simple graphs. Let \(G\) be a multigraph with the vertex set \(V(G)\) and let \(f: V(G)\to \{-1, 0,1\}\). The mapping \(f\) is called a minus-dominating function on \(G\), if for each \(v\in V(G)\) the sum of \(f(v)\) and of all \(f(u)\) for \(u\) adjacent to \(v\), each \(f(u)\) being counted as many times as the number of edges joining to \(v\), is at least \(1\). The sum of the values of \(f\) in all vertices of \(G\) is the weight \(w(f)\) of \(f\). The minimum weight of a minus-dominating function on \(G\) is the minus-domination number \(\gamma^-(G)\) of \(G\). The main theorem is the following: There are constants \(C\) and \(c> 0\) such that for all integers \(r\geq C\) and for all \(n\) that are multiples of \(4r\), there exists a bipartite \(r\)-regular \(n\)-vertex multigraph \(G\), in which each vertex has at least \(r/2\) distinct neighbours and such that \(\gamma^-(G)\geq c(n/r)\log r\).