Weighted Domination

A weighted graph \((G,w)\) is a graph \(G = (V, E)\) together with a positive weight-function on its vertices \(w: V \to \mathbf{R}^{>0}\). The weighted domination number \(\gamma_w(G)\) of \((G, w)\) is the minimum weight \(w(D) = \sum_{v \in D} w(v)\) of a vertex set \(D \subseteq V\) with \(N[D] = V\), i.e. a dominating set of \(G\).

For this natural generalization of the well-known domination number, we study some of the classical questions of domination theory. We characterize all extremal graphs for the simple Ore-like bound \(\gamma_w(G) \leq \frac{1}{2}w(V)\) and prove Nordhaus-Gaddum-type inequalities for the weighted domination number.