No label defined (Q4374702)

A two-valued function \(f\) defined on the vertices of a graph \(G=(V,E)\), \(f:V\rightarrow \{-1,1\}\), is a signed dominating function if the sum of its function values over any closed neighborhood is at least one. It is a majority dominating function if this holds true for at least half of the neighborhoods. The weight of \(f\) is the sum of its values over all vertices of \(G\). The signed (majority) domination number of \(G\), denoted by \(\gamma _s(G)\) (\(\gamma _{maj}(G)\), respectively) is the minimum weight of a signed (majority, respectively) dominating function of \(G\). It is proved that for every \(r\)-regular (\(r\geq 2\)) graph \(G\) of order \(n\), \(\gamma _s(G)\leq (\frac {(r+1)^2}{r^2+4r-1})n\) if \(r\) is odd, and \(\gamma _s(G)\leq (\frac {r+1}{r+3})n\) if \(r\) is even. The author actually proves that the weight of any minimal signed dominating function of \(G\) does not exceed this bound. The theorem concerning majority domination number says that for every \(r\)-regular (\(r\geq 2\)) graph \(G\) of order \(n\), \(\gamma _{maj}(G)\geq (\frac {1-r}{2(r+1)})n\) if \(r\) is odd, and \(\gamma _{maj}(G)\geq (\frac {-r}{2(r+1)})n\) if \(r\) is even.