Abstract
Ph.D.
In Chapter 1 we will give a brief historical account of domination theory and define the necessary concepts which we use in the remainder of the thesis.
In Chapter 2 we establish a lower bound for the minus k-subdomination number of trees and characterize those trees which achieve this lower bound. We also compute the value of Yks-101 for comets and for cycles. We then show that the decision problem corresponding to the computation of Yks-101 is NP-complete, even for bipartite graphs.
In Chapter 3 we characterize those trees T which achieve the lower bound of Cockayne and Mynhardt, thus generalizing the results of [11] and [2]. We also compute Yks-11 for comets and cycles.
In Chapter 4 we study the partial signed domination number of a graph. In particular, we establish a lower bound on Yc/d for regular graphs and prove that the decision problem corresponding to the computation of the partial signed domination number is NP-complete.
Chapter 5 features the minus bondage number b- (G) of a nonempty graph G, which is defined as the minimum cardinality of a set of edges whose removal increases the minus domination number of G. We show that the minus bondage and ordinary bondage numbers of a graph are incomparable. Exact values for certain well known classes of graphs are computed and an upper bound for b- is given for trees. Finally, we show that the decision problem corresponding to the computation of b- is N P - hard, even for bipartite graphs. We conclude, in Chapter 6, by discussing possible directions for future research.