Generalized domination and efficient domination in graphs
type: Item
instance of: scholarly article
title: Generalized domination and efficient domination in graphs
zbMATH Open document ID: 0860.05044
DOI: 10.1016/0012-365X(95)00094-D
published in: Discrete Mathematics
publication date: 1997-04-13T00:00:00Z
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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 955078
zbMATH Keywords: \(Y\)-domination function
zbMATH Keywords: \(Y\)-domination number
zbMATH Keywords: efficient \(Y\)-domination function
author: David W. Bange
author: Anthony E. Barkauskas
author: Linda H. Host
author: Peter Slater
reviewed by: Bohdan Zelinka
MaRDI profile type: Publication
cites work: Q3815323
cites work: Minus domination in graphs
cites work: Q4871151
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Q4198056
cites work: Q3032297
cites work: Q3740231
description: scientific article; zbMATH DE number 955078