Please use this identifier to cite or link to this item: http://idr.nitk.ac.in/jspui/handle/123456789/17074
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorKamath, Shyam S.-
dc.contributor.advisorThilak, A Senthil.-
dc.contributor.authorM, Rashmi.-
dc.date.accessioned2022-02-01T11:03:44Z-
dc.date.available2022-02-01T11:03:44Z-
dc.date.issued2021-
dc.identifier.urihttp://idr.nitk.ac.in/jspui/handle/123456789/17074-
dc.description.abstractThe 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.isoenen_US
dc.publisherNational Institute of Technology Karnataka, Surathkalen_US
dc.subjectDepartment of Mathematical and Computational Sciencesen_US
dc.subjectDominationen_US
dc.subjectdegreeen_US
dc.subjectk-part degree restricted dominationen_US
dc.subjectk-dominationen_US
dc.subjectCovering numberen_US
dc.subjectIndependence numberen_US
dc.subjectNP-completeen_US
dc.titleDegree Restricted Domination in Graphsen_US
dc.typeThesisen_US
Appears in Collections:1. Ph.D Theses

Files in This Item:
File Description SizeFormat 
PhD Thesis-Rashmi M (145047MA14F01).pdf2.15 MBAdobe PDFThumbnail
View/Open


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