α-Domination Original Research Article

Let G=(V,E) be any graph with n vertices, m edges and no isolated vertices. For some α with 0<α⩽1 and a set S⊆V, we say that S is α-dominating if for all v∈V−S, |N(v)∩S|⩾α|N(v)|. The size of a smallest such S is called the α-domination number and is denoted by γα(G). In this paper, we introduce α-domination, discuss bounds for γ1/2(G) for the Kingʹs graph, and give bounds for γα(G) for a general α, 0<α⩽1. Furthermore, we show that the problem of deciding whether γα(G)⩽k is NP-complete.