Degree Restricted Domination in Graphs

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.