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.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:uj/uj:3230 |
| Date | 27 August 2012 |
| Creators | Ungerer, Elna |
| Source Sets | South African National ETD Portal |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0141 seconds