Total and zero forcing in graphs

**Authors:**Davila, Randy R.**Date:**2019**Subjects:**Graphic methods**Language:**English**Type:**Doctoral (Thesis)**Identifier:**http://hdl.handle.net/10210/295628 , uj:32198**Description:**Abstract: Please refer to full text to view abstract. , D.Phil. (Mathematics)**Full Text:**

**Authors:**Davila, Randy R.**Date:**2019**Subjects:**Graphic methods**Language:**English**Type:**Doctoral (Thesis)**Identifier:**http://hdl.handle.net/10210/295628 , uj:32198**Description:**Abstract: Please refer to full text to view abstract. , D.Phil. (Mathematics)**Full Text:**

L(d,1)-labellings in graphs

**Authors:**Botha, Natascha**Date:**2015-09-16**Subjects:**Graphic methods**Type:**Thesis**Identifier:**uj:14127 , http://hdl.handle.net/10210/14564**Description:**M.Sc. , Please refer to full text to view abstract**Full Text:**

**Authors:**Botha, Natascha**Date:**2015-09-16**Subjects:**Graphic methods**Type:**Thesis**Identifier:**uj:14127 , http://hdl.handle.net/10210/14564**Description:**M.Sc. , Please refer to full text to view abstract**Full Text:**

Balanced graphs, threshold functions of random graphs and their co-occurrence

**Authors:**Maartens, Ronald John**Date:**2015**Subjects:**Graphic methods , Random graphs , Threshold logic**Language:**English**Type:**Masters (Thesis)**Identifier:**http://hdl.handle.net/10210/82556 , uj:18973**Description:**Abstract: Our main goal with this dissertation is to create a solid base on balanced and unbalanced graphs, as well as threshold functions of random graphs for future reference. We begin by performing an in depth study on balanced and unbalanced graphs as well as the two variations strictly balanced and strongly balanced as these graphs occur quite frequently in the literature of Random Graph Theory. Our purpose is to define each of these graphs and then to prove a few important results that will be used later on in the dissertation and for future reference. A very important result that we will prove here is that any graph has a balanced extension, and then we take this result even further by determining the least number of vertices and edges that are required to form a balanced extension. Thereafter we define and study threshold functions of random graphs. We begin by determining when a threshold function will exist and whether this function is unique. A step by step approach is given for the two methods of determining a threshold function, namely the First and Second Moment Method and the Grading Method, and then the first method is illustrated for both uniform random graphs and binomial random graphs. The relationship between the threshold functions of the uniform random graphs and those of the binomial random graphs are also discussed, followed by a comparison between threshold function values and extremal values... , M.Sc. (Mathematics)**Full Text:**

**Authors:**Maartens, Ronald John**Date:**2015**Subjects:**Graphic methods , Random graphs , Threshold logic**Language:**English**Type:**Masters (Thesis)**Identifier:**http://hdl.handle.net/10210/82556 , uj:18973**Description:**Abstract: Our main goal with this dissertation is to create a solid base on balanced and unbalanced graphs, as well as threshold functions of random graphs for future reference. We begin by performing an in depth study on balanced and unbalanced graphs as well as the two variations strictly balanced and strongly balanced as these graphs occur quite frequently in the literature of Random Graph Theory. Our purpose is to define each of these graphs and then to prove a few important results that will be used later on in the dissertation and for future reference. A very important result that we will prove here is that any graph has a balanced extension, and then we take this result even further by determining the least number of vertices and edges that are required to form a balanced extension. Thereafter we define and study threshold functions of random graphs. We begin by determining when a threshold function will exist and whether this function is unique. A step by step approach is given for the two methods of determining a threshold function, namely the First and Second Moment Method and the Grading Method, and then the first method is illustrated for both uniform random graphs and binomial random graphs. The relationship between the threshold functions of the uniform random graphs and those of the binomial random graphs are also discussed, followed by a comparison between threshold function values and extremal values... , M.Sc. (Mathematics)**Full Text:**

Some aspects of the theory of circulant graphs

**Authors:**Hattingh, Johannes Hendrik**Date:**2014-03-18**Subjects:**Graphic methods , Conformal geometry**Type:**Thesis**Identifier:**uj:4390 , http://hdl.handle.net/10210/9738**Description:**Ph.D. (Mathematics) , Please refer to full text to view abstract**Full Text:**

**Authors:**Hattingh, Johannes Hendrik**Date:**2014-03-18**Subjects:**Graphic methods , Conformal geometry**Type:**Thesis**Identifier:**uj:4390 , http://hdl.handle.net/10210/9738**Description:**Ph.D. (Mathematics) , Please refer to full text to view abstract**Full Text:**

Investigations into the ranks of regular graphs

**Authors:**Garner, Charles R.**Date:**2012-08-17**Subjects:**Graph theory , Graphic methods , Spectral theory (Mathematics) , Eigenvalues**Type:**Thesis**Identifier:**uj:2622 , http://hdl.handle.net/10210/6069**Description:**Ph.D. , In this thesis, the ranks of many types of regular and strongly regular graphs are determined. Also determined are ranks of regular graphs under unary operations: the line graph, the complement, the subdivision graph, the connected cycle, the complete subdivision graph, and the total graph. The binary operations considered are the Cartesian product and the complete product. The ranks of the Cartesian product of regular graphs have been investigated previously in [BBD1]; here, we summarise and extend those results to include more regular graphs. We also examine a special nonregular graph, the path. Ranks of paths and products of graphs involving paths are presented as well**Full Text:**

**Authors:**Garner, Charles R.**Date:**2012-08-17**Subjects:**Graph theory , Graphic methods , Spectral theory (Mathematics) , Eigenvalues**Type:**Thesis**Identifier:**uj:2622 , http://hdl.handle.net/10210/6069**Description:**Ph.D. , In this thesis, the ranks of many types of regular and strongly regular graphs are determined. Also determined are ranks of regular graphs under unary operations: the line graph, the complement, the subdivision graph, the connected cycle, the complete subdivision graph, and the total graph. The binary operations considered are the Cartesian product and the complete product. The ranks of the Cartesian product of regular graphs have been investigated previously in [BBD1]; here, we summarise and extend those results to include more regular graphs. We also examine a special nonregular graph, the path. Ranks of paths and products of graphs involving paths are presented as well**Full Text:**

Edge-colourings and hereditary properties of graphs

**Authors:**Dorfling, Michael Jacobus**Date:**2011-12-06**Subjects:**Graphic methods , Representations of graphs**Type:**Thesis**Identifier:**uj:1780 , http://hdl.handle.net/10210/4145**Description:**M.Sc. , The aim of this thesis is to investigate the topic of edge-colourings of graphs in the context of hereditary graph properties. We particularly aim to investigate analogues of reducibility, unique factorization and some related concepts. Chapter 1 gives the basic definitions and terminology. A few useful general results are also stated. In Chapter 2 we define and investigate decomposability, the analogue of reducibility. Some general results are first proved, such as that the indecomposability of an additive induced-hereditary property in the lattice of such properties implies that it is indecomposable in a general sense. The decomposability of various specific properties is then investigated in the rest of the chapter. In Chapter 3 we investigate unique decomposability, the analogue of unique factorization. We give examples showing that not every additive hereditary property is uniquely decomposable, and we obtain some results on homomorphism properties which lead to the unique decomposability of Ok. We also consider some related questions, such as cancellation and preservation of strict inclusions. Chapter 4 deals with Ramsey properties. We obtain some general results and, using the so-called partite construction, we obtain a few restricted Ramsey-graph results. As a corollary, we obtain two more unique decomposability results. In Chapter 5 we obtain various bounds involving the property Vk of k-degeneracy. We also investigate the sharpness of these bounds and prove that Vk is indecomposable for every k. Chapter 6 deals with the connection between colourings of infinite graphs and properties of finite graphs. We obtain some extensions of the Compactness Principle and give an example showing that the Compactness Principle can be useful in studying finite graphs.**Full Text:**

**Authors:**Dorfling, Michael Jacobus**Date:**2011-12-06**Subjects:**Graphic methods , Representations of graphs**Type:**Thesis**Identifier:**uj:1780 , http://hdl.handle.net/10210/4145**Description:**M.Sc. , The aim of this thesis is to investigate the topic of edge-colourings of graphs in the context of hereditary graph properties. We particularly aim to investigate analogues of reducibility, unique factorization and some related concepts. Chapter 1 gives the basic definitions and terminology. A few useful general results are also stated. In Chapter 2 we define and investigate decomposability, the analogue of reducibility. Some general results are first proved, such as that the indecomposability of an additive induced-hereditary property in the lattice of such properties implies that it is indecomposable in a general sense. The decomposability of various specific properties is then investigated in the rest of the chapter. In Chapter 3 we investigate unique decomposability, the analogue of unique factorization. We give examples showing that not every additive hereditary property is uniquely decomposable, and we obtain some results on homomorphism properties which lead to the unique decomposability of Ok. We also consider some related questions, such as cancellation and preservation of strict inclusions. Chapter 4 deals with Ramsey properties. We obtain some general results and, using the so-called partite construction, we obtain a few restricted Ramsey-graph results. As a corollary, we obtain two more unique decomposability results. In Chapter 5 we obtain various bounds involving the property Vk of k-degeneracy. We also investigate the sharpness of these bounds and prove that Vk is indecomposable for every k. Chapter 6 deals with the connection between colourings of infinite graphs and properties of finite graphs. We obtain some extensions of the Compactness Principle and give an example showing that the Compactness Principle can be useful in studying finite graphs.**Full Text:**

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:**

- «
- ‹
- 1
- ›
- »