scientific article; zbMATH DE number 1109393
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.
- The signed domatic number of some regular graphs
- Some remarks on the signed domatic number of graphs with small minimum degree
- Signed domination in regular graphs and set-systems
- Lower bounds on the minus domination and \(k\)-subdomination numbers.
- Minus domination number in \(k\)-partite graphs.
- Signed total domination in graphs.
- k-subdomination in graphs
- Domination graphs of regular tournaments
- Total domination versus paired-domination in regular graphs
- Inequalities relating domination parameters in cubic graphs
- Some remarks on domination in cubic graphs
- Signed domination in regular graphs
- Total minus domination in \(k\)-partite graphs
- Signed domatic number of a graph
- Partial signed domination in graphs
- Strong non split \(r\)-domination number of a graph
- Domination in Graphs
- Signed and minus dominating functions in graphs
- Regular dominating functions in regular graphs
- Signed total domatic number of a graph
- On signed distance-k-domination in graphs
- Upper bounds on the signed (k, k)-domatic number
- Lower bounds on nonnegative signed domination parameters in graphs
- Dominating functions with integer values in graphs—a survey
- Perfect domination in regular grid graphs
- DOMINATION AND REGULARITY
- On majority domination in graphs
- The power of small coalitions under two-tier majority on regular graphs
- Bounds on the signed domatic number
- Upper minus domination in a claw-free cubic graph
- Lower bounds on several versions of signed domination number
- Discrepancy and signed domination in graphs and hypergraphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4374702)
