Show simple item record

dc.contributor.advisorSwart, Henda C.
dc.contributor.advisorDankelmann, Peter A.
dc.creatorErwin, D. J.
dc.date.accessioned2012-01-25T14:06:25Z
dc.date.available2012-01-25T14:06:25Z
dc.date.created1995
dc.date.issued1995
dc.identifier.urihttp://hdl.handle.net/10413/4888
dc.descriptionThesis (M.Sc.)-University of Natal, 1995.en
dc.description.abstractThe use of characteristic functions to represent well-known sets in graph theory such as dominating, irredundant, independent, covering and packing sets - leads naturally to fractional versions of these sets and corresponding fractional parameters. Let S be a dominating set of a graph G and f : V(G)~{0,1} the characteristic function of that set. By first translating the restrictions which define a dominating set from a set-based to a function-based form, and then allowing the function f to map the vertex set to the unit closed interval, we obtain the fractional generalisation of the dominating set S. In chapter 1, known domination-related parameters and their fractional generalisations are introduced, relations between them are investigated, and Gallai type results are derived. Particular attention is given to graphs with symmetry and to products of graphs. If instead of replacing the function f : V(G)~{0,1} with a function which maps the vertex set to the unit closed interval we introduce a function f' which maps the vertex set to {0, 1, ... ,k} (where k is some fixed, non-negative integer) and a corresponding change in the restrictions on the dominating set, we obtain a k-dominating function. In chapter 2 corresponding k-parameters are considered and are related to the classical and fractional parameters. The calculations of some well known fractional parameters are expressed as optimization problems involving the k- parameters. An e = 1 function is a function f : V(G)~[0,1] which obeys the restrictions that (i) every non-isolated vertex u is adjacent to some vertex v such that f(u)+f(v) = 1, and every isolated vertex w has f(w) = 1. In chapter 3 a theory of e = 1 functions and parameters is developed. Relationships are traced between e = 1 parameters and those previously introduced, some Gallai type results are derived for the e = 1 parameters, and e = 1 parameters are determined for several classes of graphs. The e = 1 theory is applied to derive new results about classical and fractional domination parameters.en
dc.language.isoenen
dc.subjectTheses--Mathematics.en
dc.subjectGraph theory.en
dc.subjectParameter estimation.en
dc.subjectSet functions.en
dc.titleParameters related to fractional domination in graphs.en
dc.typeThesisen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record