Generalized domination and efficient domination in graphs

DOI10.1016/0012-365X(95)00094-DMaRDI QIDQ1126173zbMATH OpenFDO

Authors David W. Bange, Anthony E. Barkauskas, Linda H. Host, Peter Slater

Publication date 13 April 1997

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(95)00094-D

zbMATH Keywords

\(Y\)-domination function \(Y\)-domination number efficient \(Y\)-domination function

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Review text

The closed neighbourhood of a vertex \(v\) of a graph \(G\) is the set consisting of \(v\) and of all vertices adjacent to \(v\) in \(G\). A function \(f\) which maps the vertex set \(V(G)\) of \(G\) onto a subset \(Y\) of the set of real numbers is called \(Y\)-dominating in \(G\), if the sum of its values over the closed neighbourhood of each vertex \(v\) of \(G\) is at least 1. If it is exactly 1 for each vertex, then \(f\) is called a \(Y\)-domination function on \(G\). The weight \(w(f)\) of \(f\) is the sum of values of \(f\) over \(V(G)\). The minimum weight of a \(Y\)-domination function in \(G\) is the \(Y\)-domination number \(\gamma_Y(G)\) of \(G\). A necessary and sufficient condition for the existence of a \(Y\)-dominating function in a graph \(G\) and a sufficient condition for the existence of an efficient \(Y\)-domination function are presented. The problem to decide whether in a given graph there exists an efficient \(Y\)-domination function with \(Y=\{-1,1\}\) (the signed domination function) is shown to be NP-complete.

Recommendations

Cites work

Cited in

(42)

This page was built for publication: Generalized domination and efficient domination in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1126173)