Generalized chromatic numbers and invariants of hereditary graph properties

**Authors:**Dorfling, Samantha**Date:**2011-12-06**Subjects:**Invariants , Graphic methods , Graph theory**Type:**Thesis**Identifier:**uj:1784 , http://hdl.handle.net/10210/4149**Description:**D. Phil (Mathematics) , In this thesis we investigate generalized chromatic numbers in the context of hereditary graph properties. We also investigate the general topic of invariants of graphs as well as graph properties. In Chapter 1 we give relevant definitions and terminology pertaining to graph properties. In Chapter 2 we investigate generalized chromatic numbers of some well-known additive hereditary graph properties. This problem necessitates the investigation of reducible bounds. One of the results here is an improvement on a known upper bound for the path partition number of the property Wk. We also look at the generalized chromatic number of infinite graphs and hereby establish the connection between the generalized chromatic number of properties and infinite graphs. In Chapter 3 the analogous question of the generalized edge-chromatic number of some well-known additive hereditary properties is investigated. Similarly we find decomposable bounds and are also able to find generalized edge-chromatic numbers of properties using some well-known decomposable bounds. In Chapter 4 we investigate the more general topic of graph invariants and the role they play in chains of graph properties and then conversely the invariants that arise from chains of graph properties. Moreover we investigate the effects on monotonicity of the invariants versus heredity and additivity of graph properties. In Chapter 5 the general topic of invariants of graph properties defined in terms of the set of minimal forbidden subgraphs of the properties is studied. This enables us to investigate invariants so defined on binary operations between graph properties. In Chapter 6 the notion of natural and near-natural invariants are introduced and are also studied on binary operations of graph properties. The set of minimal forbidden subgraphs again plays a role in the definition of invariants here and this then leads us to study the completion number of a property.**Full Text:**

**Authors:**Dorfling, Samantha**Date:**2011-12-06**Subjects:**Invariants , Graphic methods , Graph theory**Type:**Thesis**Identifier:**uj:1784 , http://hdl.handle.net/10210/4149**Description:**D. Phil (Mathematics) , In this thesis we investigate generalized chromatic numbers in the context of hereditary graph properties. We also investigate the general topic of invariants of graphs as well as graph properties. In Chapter 1 we give relevant definitions and terminology pertaining to graph properties. In Chapter 2 we investigate generalized chromatic numbers of some well-known additive hereditary graph properties. This problem necessitates the investigation of reducible bounds. One of the results here is an improvement on a known upper bound for the path partition number of the property Wk. We also look at the generalized chromatic number of infinite graphs and hereby establish the connection between the generalized chromatic number of properties and infinite graphs. In Chapter 3 the analogous question of the generalized edge-chromatic number of some well-known additive hereditary properties is investigated. Similarly we find decomposable bounds and are also able to find generalized edge-chromatic numbers of properties using some well-known decomposable bounds. In Chapter 4 we investigate the more general topic of graph invariants and the role they play in chains of graph properties and then conversely the invariants that arise from chains of graph properties. Moreover we investigate the effects on monotonicity of the invariants versus heredity and additivity of graph properties. In Chapter 5 the general topic of invariants of graph properties defined in terms of the set of minimal forbidden subgraphs of the properties is studied. This enables us to investigate invariants so defined on binary operations between graph properties. In Chapter 6 the notion of natural and near-natural invariants are introduced and are also studied on binary operations of graph properties. The set of minimal forbidden subgraphs again plays a role in the definition of invariants here and this then leads us to study the completion number of a property.**Full Text:**

Domination in graphs with bounded degrees

**Authors:**Dorfling, Samantha**Date:**2012-09-10**Subjects:**Graph theory. , Combinatorial analysis.**Type:**Thesis**Identifier:**uj:9885 , http://hdl.handle.net/10210/7284**Description:**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.**Full Text:**

**Authors:**Dorfling, Samantha**Date:**2012-09-10**Subjects:**Graph theory. , Combinatorial analysis.**Type:**Thesis**Identifier:**uj:9885 , http://hdl.handle.net/10210/7284**Description:**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.**Full Text:**

- «
- ‹
- 1
- ›
- »