Please use this identifier to cite or link to this item:
http://idr.nitk.ac.in/jspui/handle/123456789/17074
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | Kamath, Shyam S. | - |
dc.contributor.advisor | Thilak, A Senthil. | - |
dc.contributor.author | M, Rashmi. | - |
dc.date.accessioned | 2022-02-01T11:03:44Z | - |
dc.date.available | 2022-02-01T11:03:44Z | - |
dc.date.issued | 2021 | - |
dc.identifier.uri | http://idr.nitk.ac.in/jspui/handle/123456789/17074 | - |
dc.description.abstract | The thesis mainly involves the study of a new generalization of the domination parameter, kpart degree restricted domination, defined by imposing a restriction on the degree of the vertices in a dominating set. A dominating set D of a graph G is a k-part degree restricted dominating set (k-DRD set), if for all u 2 D, there exists a set Cu ✓ N(u) \ (V D) such that |Cu| ld(u) k m and S u2D Cu = V D. The minimum cardinality of a k-part degree restricted dominating set of a graph G is the k-part degree restricted domination number of G. The thesis includes the detailed study of the k-part degree restricted domination and a particular case when k = 2. Bounds on the k-part degree restricted domination number in terms of covering and independence number. Relation between k-part degree restricted dominating set and some other domination invariants are discussed in the thesis. Further, the complexity of k-part degree restricted domination problem is discussed in detail. The problem of finding minimum k-part degree restricted domination number is proved to be NP-complete for bipartite graphs, chordal graphs, undirected path graphs, chordal bipartite graphs, circle graphs, planar graphs and even when restricted to split graphs. Also, exhibit a polynomial time algorithm to find a minimum k-part degree restricted domination number of trees and an exponential time algorithm to find a minimum k-part degree restricted domination number of interval graphs. The critical aspects of the k-part degree restricted domination number is provided with respect to the removal of vertices and edges from the graph. | en_US |
dc.language.iso | en | en_US |
dc.publisher | National Institute of Technology Karnataka, Surathkal | en_US |
dc.subject | Department of Mathematical and Computational Sciences | en_US |
dc.subject | Domination | en_US |
dc.subject | degree | en_US |
dc.subject | k-part degree restricted domination | en_US |
dc.subject | k-domination | en_US |
dc.subject | Covering number | en_US |
dc.subject | Independence number | en_US |
dc.subject | NP-complete | en_US |
dc.title | Degree Restricted Domination in Graphs | en_US |
dc.type | Thesis | en_US |
Appears in Collections: | 1. Ph.D Theses |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
PhD Thesis-Rashmi M (145047MA14F01).pdf | 2.15 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.