Minus domination in small-degree graphs

AbstractMinus domination in graphs is a variant of domination where the vertices must be labeled −1,0,+1 such that the sum of labels in each N[v] is positive. (As usual, N[v] means the set containing v together with its neighbors.) The minus domination number γ− is the minimum total sum of labels that can be achieved. In this paper we prove linear lower bounds for γ− in graphs either with Δ⩽3, or with Δ⩽4 but without vertices of degree 2. The central section is concerned with complexity results for Δ⩽4: We show that computing γ− is NP-hard and MAX SNP-hard there, but that γ− can be approximated in linear time within some constant factor. Finally, our approach also applies to signed domination (where the labels are −1,+1 only) in small-degree graphs