Generalized domination and efficient domination in graphs

✍ Scribed by D.W. Bange; A.E. Barkauskas; L.H. Host; P.J. Slater

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 516 KB
• Volume: 159
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00094-d

✦ Synopsis

This paper generalizes dominating and efficient dominating sets of a graph. Let G be a graph with vertex set V(G). If f: V(G) ~ Y, where Y is a subset of the reals, the weight off is the sum of f(v) over all ve V(G). If the closed neighborhood sum off(v) at every vertex is at least 1, thenfis called a Y-dominating function of G. If the closed neighborhood sum is exactly 1 at every vertex, then f is called an efficient dominating function. Two Y-dominating functions are equivalent if they have the same closed neighborhood sum at every vertex of G. It is shown that if the closed neighborhood matrix of G is invertiable then G has an efficient Y-dominating function for some Y. It is also shown that G has an efficient Y-dominating function if and only if all equivalent Y-dominating functions have the same weight. Related theoretical and computational questions are considered in the special cases where Y = { -1, 1} or Y = { -1, 0, 1}.