UJDigispace Repository

Domination in graphs with bounded degrees

Show simple item record

dc.contributor.advisor Jonck, E. Dr. ; Broere, I., Prof. en_US
dc.contributor.author Dorfling, Samantha
dc.date.accessioned 2012-09-10T09:33:58Z
dc.date.available 2012-09-10T09:33:58Z
dc.date.issued 2012-09-10
dc.date.submitted 1998
dc.identifier.uri http://hdl.handle.net/10210/7284
dc.description M.Sc. en_US
dc.description.abstract 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. en_US
dc.language.iso en en_US
dc.subject Graph theory. en_US
dc.subject Combinatorial analysis. en_US
dc.title Domination in graphs with bounded degrees en_US
dc.type Thesis en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search UJDigispace


My Account