Please use this identifier to cite or link to this item:
Title: Algorithmic aspects of k-part degree restricted domination in graphs
Authors: Kamath S.S.
Senthil Thilak A.
Rashmi M.
Issue Date: 2020
Citation: Discrete Mathematics, Algorithms and Applications , Vol. 12 , 5 , p. -
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.
Appears in Collections:1. Journal Articles

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.