α-Domination

Let G = (V,E) be any graph with n vertices, m edges and no isolated vertices. For some alpha with 0 < alpha less than or equal to 1 and a set S subset of or equal to V, we say that S is alpha-dominating if for all nu epsilon V - S, \ N(nu)boolean AND S \greater than or equal to alpha \ N(nu)\. The size of a smallest such S is called the alpha-domination number and is denoted by gamma(x)(G). In this paper, we introduce alpha-domination, discuss bounds for gamma(1/2)(G) for the King's graph, and give bounds for (gamma alpha)(G) for a general alpha, 0 < alpha less than or equal to 1. Furthermore, we show that the problem of deciding whether gamma(alpha)(G) less than or equal to k is NP-complete. (C) 2000 Elsevier Science B.V. All rights reserved.