The -Adjacency Domination in Graphs

Let be a simple and undirected graph with vertex set . A set is called a dominating set of if every vertexoutside is adjacent to at least one vertex of . For any integer , a dominating set is called a -adjacencydominating set of if the induced subgraph contains at least one vertex of degree at most . The minimumcardinality of a - adjacency dominating set of is called the - adjacency domination number of that isdenoted by . In this paper, the study of - adjacency domination in graphs is initiated, and exact values andsome bounds on the - adjacency domination number of a given graph are presented. Furthermore, it isshown that there is a polynomial-time algorithm that computes the -adjacency domination number of agiven tree. Moreover, it is proven that the decision problem associated to the -adjacency domination isNP-complete for bipartite graphs.