Pure Mathematics

Permanent URI for this communityhttps://hdl.handle.net/10413/6770

Browse

Now showing 1 - 3 of 3

Aspects of distance measures in graphs.
(2011) Ali, Patrick Yawadu.; Dankelmann, Peter A.; Mukwembi, Simon.
In this thesis we investigate bounds on distance measures, namely, Steiner diameter and radius, in terms of other graph parameters. The thesis consists of four chapters. In Chapter 1, we define the most significant terms used throughout the thesis, provide an underlying motivation for our research and give background in relevant results. Let G be a connected graph of order p and S a nonempty set of vertices of G. Then the Steiner distance d(S) of S is the minimum size of a connected subgraph of G whose vertex set contains S. If n is an integer, 2 ≤ n ≤ p, the Steiner n-diameter, diamn(G), of G is the maximum Steiner distance of any n-subset of vertices of G. In Chapter 2, we give a bound on diamn(G) for a graph G in terms of the order of G and the minimum degree of G. Our result implies a bound on the ordinary diameter by Erdös, Pach, Pollack and Tuza. We obtain improved bounds on diamn(G) for K3-free graphs and C4-free graphs. In Chapter 3, we prove that, if G is a 3-connected plane graph of order p and maximum face length l then the radius of G does not exceed p/6 + 5l/6 + 5/6. For constant l, our bound improves on a bound by Harant. Furthermore we extend these results to 4- and 5-connected planar graphs. Finally, we complete our study in Chapter 4 by providing an upper bound on diamn(G) for a maximal planar graph G.
Bounds on distance parameters of graphs.
(2007) Van den Berg, Paul.; Swart, Hendrika Cornelia Scott.; Dankelmann, Peter A.
No abstract available.
Parameters related to fractional domination in graphs.
(1995) Erwin, D. J.; Swart, Hendrika Cornelia Scott.; Dankelmann, Peter A.
The 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.

Browse

Browsing Pure Mathematics by Author "Dankelmann, Peter A."