No description available.

Ph.D. (Mathematics) / Please refer to full text to view abstract

Ph.D. (Mathematics) / Please refer to full text to view abstract

The well studied class of irredundant vertex sets of a graph has been previously shown to be a special case of (a) a “Private Neighbor Cube” of eight classes of vertex subsets and (b) a family of sixty four classes of “generalised irredundant sets.” The thesis makes various advances in the theory of irredundance. More specifically: (i) Nordhaus-Gaddum results for all the sixty-four classes of generalised irredundant sets are obtained. (ii) Sharp lower bounds involving order and maximum degree are attained for two specific classes in the Private Neighbor Cube. (iii) A new framework which includes both of the above generalisations and various concepts of domination, is proposed. / Graduate

Thesis (MSc)--University of Stellenbosch, 2007. / Bibliography. Also available via the Internet.

Ph.D. / In this thesis, our primary objective is to investigate the effects that various graph modifications have on the total domination number of a graph. In Chapter 1, we introduce basic graph theory concepts and preliminary definitions. In Chapters 2 and 3, we investigate the graph modification of edge removal. In Chapter 2, we characterize graphs for which the removal of any arbitrary edge increases the total domination number. We also begin the investigation of graphs for which the removal of any arbitrary edge has no effect on the total domination number. In Chapter 3, we continue this investigation and determine the minimum number of edges required for these graphs. The contents of Chapters 2 and 3 have been published in Discrete Applied Mathematics [15] and [16]. In Chapter 4, we investigate the graph modification of edge addition. In particular, we focus our attention on graphs for which adding an edge between any pair of nonadjacent vertices has no effect on the total domination number. We characterize these graphs, determine a sharp upper bound on their total domination number and determine which combinations of order and total domination number are attainable. 10 11 We also study claw-free graphs which have this property. The contents of this chapter were published in Discrete Mathematics [20]. In Chapter 5, we investigate the graph modification of vertex removal. We characterize graphs for which the removal of any vertex changes the total domination number and find sharp upper and lower bounds on the total domination number of these graphs. We also characterize graphs for which the removal of an arbitrary vertex has no effect on the total domination number and we further show that they have no forbidden subgraphs. The contents of this chapter were published in Discrete Applied Mathematics [14]. In Chapters 6 and 7, we investigate the graph modification of edge lifting. In Chapter 6, we show that there are no trees for which every possible edge lift decreases the domination number, and we characterize trees for which every possible edge lift increases the domination number. The contents of Chapter 6 were published in the journal Quaestiones Mathematicae [17]. In Chapter 7, we show that there are no trees for which every possible edge lift decreases the total domination number and that there are no trees for which every possible edge lift leaves the total domination number unchanged. We characterize trees for which every possible edge lift increases the total domination number. At the time of the writing of this thesis, the contents of Chapter 7 have been published online in the Journal of Combinatorial Optimization [18] and will appear in print in a future issue.

D.Phil. / Domination in graphs is now well studied in graph theory and the literature on this subject has been surveyed and detailed in the two books by Haynes, Hedetniemi, and Slater [45, 46]. In this thesis, we continue the study of domination, by adding to the theory; improving a number of known bounds and solving two previously published conjectures. With the exception of the introduction, each chapter in this thesis corresponds to a single paper already published or submitted as a journal article. Despite the seeming disparity in the content of some of these articles, there are two overarching goals achieved in this thesis. The rst is an attempt to partition the vertex set of a graph into two sets, each holding a speci c domination-type property. The second is simply to improve known bounds for various domination parameters. In particular, an edge weighting function is presented which has been useful in providing some of these bounds. Although the research began as two separate areas of focus, there has been a fair degree of overlap and a number of the results contained in this thesis bridge the gap quite pleasingly. Specially, Chapter 11 uses the edge weighting function to prove a bound on one of the sets in our most fundamental partitions, while the improvement on a known bound presented in Chapter 7 was inspired by considering the possible existence of another partition. This latter proof relies implicitly on the `almost' existence of such a partition.

Thesis (Ph.D.)--University of Nebraska-Lincoln, 2006. / Title from title screen (site viewed on Feb. 5, 2007). PDF text: 66 p. : ill. (some col.) UMI publication number: AAT 3216432. Includes bibliographical references. Also available in microfilm and microfiche format.

Thesis (Ph. D.)--University of Stellenbosch, 2004. / Includes bibliographical references. Also available via the Internet.

For a graph G = (V (G), E (G)), a set S ~ V (G) dominates G if each vertex in V (G) \S is adjacent to a vertex in S. The domination number I (G) (independent domination number i (G)) of G is the minimum cardinality amongst its dominating sets (independent dominating sets). G is k-edge-domination-critical, abbreviated k-1- critical, if the domination number k decreases whenever an edge is added. Further, G is hamiltonian if it has a cycle that passes through each of its vertices. This dissertation assimilates research generated by two conjectures: Conjecture I. Every 3-1-critical graph with minimum degree at least two is hamiltonian. Conjecture 2. If G is k-1-critical, then I ( G) = i ( G). The recent proof of Conjecture I is consolidated and presented accessibly. Conjecture 2 remains open for k = 3 and has been disproved for k :::>: 4. The progress is detailed and proofs of new results are presented. / Mathematical Science / M. Sc. (Mathematics)