M.Sc. / Let G be a graph and D a set of vertices such that every vertex in G is in D or adjacent to at least one vertex in D. Then D is called a dominating set of G and the smallest cardinality of such a dominating set of G is known as the domination number of G, denoted by y(G). This short dissertation is a study of the domination number in graphs with bounds on both the minimum and maximum degrees. In Chapter 1 we give all definitions, terminology and references related to the material presented in this thesis. In Chapter 2 we study an article by McCuaig and Shepherd which considers graphs with minimum degree two and gives an upper bound for their domination numbers in terms of their order. This bound is also an improvement of one originally determined by Ore. In Chapter 3 an article by Fisher, Fraughnaugh and Seager is studied. Here the domination number in graphs with maximum degree at most three is discussed. Furthermore au upper bound on the domination number of a graph is given in terms of its order, size and the number of isolated vertices it contains. This result is an extension of a previous result by Reed on domination in graphs with minimum degree three. A set U of vertices of a graph G = (V, E) is k-dominating if each vertex of V — U is adjacent to at least k vertices of U. The k-domination number of G, Yk (G), is the smallest cardinality of a k-dominating set of G. Finally in Chapter 4 we study an article by Cockayne, Gamble and Shepherd which gives an upper bound for the k-domination number of a graph with minimum degree at least k. This result is a generalization of a result by Ore.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:uj/uj:9885 |
| Date | 10 September 2012 |
| Creators | Dorfling, Samantha |
| Source Sets | South African National ETD Portal |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0022 seconds