# Aspects of functional variations of domination in graphs.

## UKZN ResearchSpace

 dc.contributor.advisor Henning, Michael A. dc.contributor.advisor Hattingh, Johannes H. dc.creator Harris, Laura Marie. dc.date.accessioned 2012-10-22T12:05:14Z dc.date.available 2012-10-22T12:05:14Z dc.date.created 2003 dc.date.issued 2003 dc.identifier.uri http://hdl.handle.net/10413/7384 dc.description Thesis (Ph.D.)-University of Natal, Pietermaritzburg, 2003. en dc.description.abstract Let G = (V, E) be a graph. For any real valued function f : V >R and SCV, let f (s) = z ues f(u). The weight of f is defined as f(V). A signed k-subdominating function (signed kSF) of G is defined as a function f : V > {-I, I} such that f(N[v]) > 1 for at least k vertices of G, where N[v] denotes the closed neighborhood of v. The signed k-subdomination number of a graph G, denoted by yks-11(G), is equal to min{f(V) I f is a signed kSF of G}. If instead of the range {-I, I}, we require the range {-I, 0, I}, then we obtain the concept of a minus k-subdominating function. Its associated parameter, called the minus k-subdomination number of G, is denoted by ytks-101(G). In chapter 2 we survey recent results on signed and minus k-subdomination in graphs. In Chapter 3, we compute the signed and minus k-subdomination numbers for certain complete multipartite graphs and their complements, generalizing results due to Holm [30]. In Chapter 4, we give a lower bound on the total signed k-subdomination number in terms of the minimum degree, maximum degree and the order of the graph. A lower bound in terms of the degree sequence is also given. We then compute the total signed k-subdomination number of a cycle, and present a characterization of graphs G with equal total signed k-subdomination and total signed l-subdomination numbers. Finally, we establish a sharp upper bound on the total signed k-subdomination number of a tree in terms of its order n and k where 1 < k < n, and characterize trees attaining these bounds for certain values of k. For this purpose, we first establish the total signed k-subdomination number of simple structures, including paths and spiders. In Chapter 5, we show that the decision problem corresponding to the computation of the total minus domination number of a graph is NP-complete, even when restricted to bipartite graphs or chordal graphs. For a fixed k, we show that the decision problem corresponding to determining whether a graph has a total minus domination function of weight at most k may be NP-complete, even when restricted to bipartite or chordal graphs. Also in Chapter 5, linear time algorithms for computing Ytns-11(T) and Ytns-101(T) for an arbitrary tree T are presented, where n = n(T). In Chapter 6, we present cubic time algorithms to compute Ytks-11(T) and Ytks-101l(T) for a tree T. We show that the decision problem corresponding to the computation of Ytks-11(G) is NP-complete, and that the decision problem corresponding to the computation of Ytks-101 (T) is NP-complete, even for bipartite graphs. In addition, we present cubic time algorithms to computeYks-11(T) and Yks-101(T) for a tree T, solving problems appearing in [25]. en dc.language.iso en_ZA en dc.subject Graphic Methods. en dc.subject Graph Theory. en dc.subject Mathematics--Data Processing. en dc.subject Theses--Mathematics. en dc.title Aspects of functional variations of domination in graphs. en dc.type Thesis en