Algorithmic aspects of k-part degree restricted domination in graphs

Abstract

The concept of network is predominantly used in several applications of computer communication networks. It is also a fact that the dominating set acts as a virtual backbone in a communication network. These networks are vulnerable to breakdown due to various causes, including traffic congestion. In such an environment, it is necessary to regulate the traffic so that these vulnerabilities could be reasonably controlled. Motivated by this, k-part degree restricted domination is defined as follows. For a positive integer k, a dominating set D of a graph G is said to be a k-part degree restricted dominating set (k-DRD set) if for all u ∈ D, there exists a set Cu ⊆ N(u) ∩(V − D) such that |Cu| ≤ ⌈d(ku) ⌉ and Su∈D Cu = V − D. The minimum cardinality of a k-DRD set of a graph G is called the k-part degree restricted domination number of G and is denoted by γ dk (G). In this paper, we present a polynomial time reduction that proves the NP-completeness of the k-part degree restricted domination problem for bipartite graphs, chordal graphs, undirected path graphs, chordal bipartite graphs, circle graphs, planar graphs and split graphs. We propose a polynomial time algorithm to compute a minimum k-DRD set of a tree and minimal k-DRD set of a graph. © 2020 World Scientific Publishing Co. Pte Ltd. All rights reserved.