Please use this identifier to cite or link to this item: https://idr.l2.nitk.ac.in/jspui/handle/123456789/16570
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKamath S.S.
dc.contributor.authorSenthil Thilak A.
dc.contributor.authorRashmi M.
dc.date.accessioned2021-05-05T10:30:53Z-
dc.date.available2021-05-05T10:30:53Z-
dc.date.issued2020
dc.identifier.citationDiscrete Mathematics, Algorithms and Applications , Vol. 12 , 5 , p. -en_US
dc.identifier.urihttps://doi.org/10.1142/S1793830920500573
dc.identifier.urihttp://idr.nitk.ac.in/jspui/handle/123456789/16570-
dc.description.abstractThe 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.en_US
dc.titleAlgorithmic aspects of k-part degree restricted domination in graphsen_US
dc.typeArticleen_US
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.