Show simple item record

dc.contributor.advisorHenning, Michael A.
dc.contributor.advisorHattingh, Johannes H.
dc.creatorHarris, Laura Marie.
dc.date.accessioned2012-10-22T12:05:14Z
dc.date.available2012-10-22T12:05:14Z
dc.date.created2003
dc.date.issued2003
dc.identifier.urihttp://hdl.handle.net/10413/7384
dc.descriptionThesis (Ph.D.)-University of Natal, Pietermaritzburg, 2003.en
dc.description.abstractLet 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.isoen_ZAen
dc.subjectGraphic Methods.en
dc.subjectGraph Theory.en
dc.subjectMathematics--Data Processing.en
dc.subjectTheses--Mathematics.en
dc.titleAspects of functional variations of domination in graphs.en
dc.typeThesisen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record