Aspects of total restrained domination in graphs

**Authors:**Joubert, Ernest**Date:**2009-03-31T09:24:15Z**Subjects:**Graph theory**Type:**Thesis**Identifier:**http://ujcontent.uj.ac.za8080/10210/371446 , uj:8243 , http://hdl.handle.net/10210/2354**Description:**D.Phil.**Full Text:**

**Authors:**Joubert, Ernest**Date:**2009-03-31T09:24:15Z**Subjects:**Graph theory**Type:**Thesis**Identifier:**http://ujcontent.uj.ac.za8080/10210/371446 , uj:8243 , http://hdl.handle.net/10210/2354**Description:**D.Phil.**Full Text:**

Total domination in graphs and graph modifications

**Authors:**Desormeaux, Wyatt Jules**Date:**2012-08-20**Subjects:**Graph theory , Domination (Graph theory)**Type:**Thesis**Identifier:**http://ujcontent.uj.ac.za8080/10210/385330 , uj:2717 , http://hdl.handle.net/10210/6158**Description:**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.**Full Text:**

**Authors:**Desormeaux, Wyatt Jules**Date:**2012-08-20**Subjects:**Graph theory , Domination (Graph theory)**Type:**Thesis**Identifier:**http://ujcontent.uj.ac.za8080/10210/385330 , uj:2717 , http://hdl.handle.net/10210/6158**Description:**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.**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:**

Paired-domination in graphs

**Authors:**McCoy, John Patrick**Date:**2013-07-24**Subjects:**Paired-domination , Graph theory**Type:**Thesis**Identifier:**uj:7689 , http://hdl.handle.net/10210/8556**Description:**D.Phil. (Mathematics) , Domination and its variants are now well studied in graph theory. One of these variants, paired-domination, requires that the subgraph induced by the dominating set contains a perfect matching. In this thesis, we further investigate the concept of paired-domination. Chapters 2, 3, 4, and 5 of this thesis have been published in [17], [41], [42], and [43], respectively, while Chapter 6 is under submission; see [44]. In Chapter 1, we introduce the domination parameters we use, as well as the necessary graph theory terminology and notation. We combine the de nition of a paired-dominating set and a locating set to de ne three new sets: locating-paired- dominating sets, di erentiating-paired-dominating sets, and metric-locating-paired- dominating sets. We use these sets in Chapters 3 and 4. In Chapter 2, we investigate the relationship between the upper paired-domination and upper total domination numbers of a graph. In Chapter 3, we study the properties of the three kinds of locating paired-dominating sets we de ned, and in Chapter 4 we give a constructive characterisation of those trees which do not have a di erentiating- paired-dominating set. In Chapter 5, we study the problem of characterising planar graphs with diameter two and paired-domination number four. Lastly, in Chap- ter 6, we establish an upper bound on the size of a graph of given order and paired- domination number and we characterise the extremal graphs that achieve equality in the established bound.**Full Text:**

**Authors:**McCoy, John Patrick**Date:**2013-07-24**Subjects:**Paired-domination , Graph theory**Type:**Thesis**Identifier:**uj:7689 , http://hdl.handle.net/10210/8556**Description:**D.Phil. (Mathematics) , Domination and its variants are now well studied in graph theory. One of these variants, paired-domination, requires that the subgraph induced by the dominating set contains a perfect matching. In this thesis, we further investigate the concept of paired-domination. Chapters 2, 3, 4, and 5 of this thesis have been published in [17], [41], [42], and [43], respectively, while Chapter 6 is under submission; see [44]. In Chapter 1, we introduce the domination parameters we use, as well as the necessary graph theory terminology and notation. We combine the de nition of a paired-dominating set and a locating set to de ne three new sets: locating-paired- dominating sets, di erentiating-paired-dominating sets, and metric-locating-paired- dominating sets. We use these sets in Chapters 3 and 4. In Chapter 2, we investigate the relationship between the upper paired-domination and upper total domination numbers of a graph. In Chapter 3, we study the properties of the three kinds of locating paired-dominating sets we de ned, and in Chapter 4 we give a constructive characterisation of those trees which do not have a di erentiating- paired-dominating set. In Chapter 5, we study the problem of characterising planar graphs with diameter two and paired-domination number four. Lastly, in Chap- ter 6, we establish an upper bound on the size of a graph of given order and paired- domination number and we characterise the extremal graphs that achieve equality in the established bound.**Full Text:**

On the chromatic number of commutative rings with identity

**Authors:**Swarts, Jacobus Stephanus**Date:**2012-08-27**Subjects:**Commutative rings , Graph theory**Type:**Thesis**Identifier:**uj:3247 , http://hdl.handle.net/10210/6656**Description:**M.Sc. , This thesis is concerned with one possible interplay between commutative algebra and graph theory. Specifically, we associate with a commutative ring R a graph and then set out to determine how the ring's properties influence the chromatic and clique numbers of the graph. The graph referred to is obtained by letting each ring element be represented by a vertex in the graph and joining two vertices when the product of their corresponding ring elements is equal to zero. The thesis focuses on rings that have a finite chromatic number, where the chromatic number of the ring is equal to the chromatic number of the associated graph. The nilradical of the ring plays a prominent role in these- investigations. Furthermore, the thesis also discusses conditions under which the chromatic and clique numbers of the associated graph are equal. The thesis ends with a discussion of rings with low (< 5) chromatic number and an example of a ring with clique number 5 and chromatic number 6.**Full Text:**

**Authors:**Swarts, Jacobus Stephanus**Date:**2012-08-27**Subjects:**Commutative rings , Graph theory**Type:**Thesis**Identifier:**uj:3247 , http://hdl.handle.net/10210/6656**Description:**M.Sc. , This thesis is concerned with one possible interplay between commutative algebra and graph theory. Specifically, we associate with a commutative ring R a graph and then set out to determine how the ring's properties influence the chromatic and clique numbers of the graph. The graph referred to is obtained by letting each ring element be represented by a vertex in the graph and joining two vertices when the product of their corresponding ring elements is equal to zero. The thesis focuses on rings that have a finite chromatic number, where the chromatic number of the ring is equal to the chromatic number of the associated graph. The nilradical of the ring plays a prominent role in these- investigations. Furthermore, the thesis also discusses conditions under which the chromatic and clique numbers of the associated graph are equal. The thesis ends with a discussion of rings with low (< 5) chromatic number and an example of a ring with clique number 5 and chromatic number 6.**Full Text:**

Lattices of graph properties

**Authors:**Moagi, Samuel John Teboho**Date:**2012-09-11**Subjects:**Graph theory , Graph theory - Problems, exercises, etc**Type:**Mini-Dissertation**Identifier:**uj:10072 , http://hdl.handle.net/10210/7459**Description:**M.Sc. , In this work we will need the basic knowledge of Graph Theory as our background and as we go along we will state and prove some of the Lattice and Set Theory results. Every graph in this work is considered as a finite simple graph, in other words, it is finite, undirected, loopless and without multiple edges. The class of all finite simple graphs will be denoted by I. If G is graph in I, we use the notation V(G) to denote the set of all vertices in G and the notation E(G) to denote the set of all the edges in G.**Full Text:**

**Authors:**Moagi, Samuel John Teboho**Date:**2012-09-11**Subjects:**Graph theory , Graph theory - Problems, exercises, etc**Type:**Mini-Dissertation**Identifier:**uj:10072 , http://hdl.handle.net/10210/7459**Description:**M.Sc. , In this work we will need the basic knowledge of Graph Theory as our background and as we go along we will state and prove some of the Lattice and Set Theory results. Every graph in this work is considered as a finite simple graph, in other words, it is finite, undirected, loopless and without multiple edges. The class of all finite simple graphs will be denoted by I. If G is graph in I, we use the notation V(G) to denote the set of all vertices in G and the notation E(G) to denote the set of all the edges in G.**Full Text:**

Aspects of signed and minus domination in graphs

**Authors:**Ungerer, Elna**Date:**2012-08-27**Subjects:**Graph theory , Combinatorial analysis**Type:**Thesis**Identifier:**uj:3230 , http://hdl.handle.net/10210/6640**Description:**Ph.D. , In Chapter 1 we will give a brief historical account of domination theory and define the necessary concepts which we use in the remainder of the thesis. In Chapter 2 we establish a lower bound for the minus k-subdomination number of trees and characterize those trees which achieve this lower bound. We also compute the value of Yks-101 for comets and for cycles. We then show that the decision problem corresponding to the computation of Yks-101 is NP-complete, even for bipartite graphs. In Chapter 3 we characterize those trees T which achieve the lower bound of Cockayne and Mynhardt, thus generalizing the results of [11] and [2]. We also compute Yks-11 for comets and cycles. In Chapter 4 we study the partial signed domination number of a graph. In particular, we establish a lower bound on Yc/d for regular graphs and prove that the decision problem corresponding to the computation of the partial signed domination number is NP-complete. Chapter 5 features the minus bondage number b- (G) of a nonempty graph G, which is defined as the minimum cardinality of a set of edges whose removal increases the minus domination number of G. We show that the minus bondage and ordinary bondage numbers of a graph are incomparable. Exact values for certain well known classes of graphs are computed and an upper bound for b- is given for trees. Finally, we show that the decision problem corresponding to the computation of b- is N P - hard, even for bipartite graphs. We conclude, in Chapter 6, by discussing possible directions for future research.**Full Text:**

**Authors:**Ungerer, Elna**Date:**2012-08-27**Subjects:**Graph theory , Combinatorial analysis**Type:**Thesis**Identifier:**uj:3230 , http://hdl.handle.net/10210/6640**Description:**Ph.D. , In Chapter 1 we will give a brief historical account of domination theory and define the necessary concepts which we use in the remainder of the thesis. In Chapter 2 we establish a lower bound for the minus k-subdomination number of trees and characterize those trees which achieve this lower bound. We also compute the value of Yks-101 for comets and for cycles. We then show that the decision problem corresponding to the computation of Yks-101 is NP-complete, even for bipartite graphs. In Chapter 3 we characterize those trees T which achieve the lower bound of Cockayne and Mynhardt, thus generalizing the results of [11] and [2]. We also compute Yks-11 for comets and cycles. In Chapter 4 we study the partial signed domination number of a graph. In particular, we establish a lower bound on Yc/d for regular graphs and prove that the decision problem corresponding to the computation of the partial signed domination number is NP-complete. Chapter 5 features the minus bondage number b- (G) of a nonempty graph G, which is defined as the minimum cardinality of a set of edges whose removal increases the minus domination number of G. We show that the minus bondage and ordinary bondage numbers of a graph are incomparable. Exact values for certain well known classes of graphs are computed and an upper bound for b- is given for trees. Finally, we show that the decision problem corresponding to the computation of b- is N P - hard, even for bipartite graphs. We conclude, in Chapter 6, by discussing possible directions for future research.**Full Text:**

On the packing chromatic numbers of some infinite product graphs

**Authors:**Lessing, De Villiers**Date:**2017**Subjects:**Graph theory , Graph coloring**Language:**English**Type:**Masters (Thesis)**Identifier:**http://hdl.handle.net/10210/269455 , uj:28628**Description:**M.Sc. (Mathematics) , Abstract: Please refer to full text to view abstract.**Full Text:**

**Authors:**Lessing, De Villiers**Date:**2017**Subjects:**Graph theory , Graph coloring**Language:**English**Type:**Masters (Thesis)**Identifier:**http://hdl.handle.net/10210/269455 , uj:28628**Description:**M.Sc. (Mathematics) , Abstract: Please refer to full text to view abstract.**Full Text:**

On the packing chromatic numbers of regular graphs

**Authors:**Nkuna, Oscar**Date:**2017**Subjects:**Graph theory , Graph coloring**Language:**English**Type:**Masters (Thesis)**Identifier:**http://hdl.handle.net/10210/279401 , uj:30004**Description:**M.Sc. (Mathematics) , Abstract: Please refer to full text to view abstract.**Full Text:**

**Authors:**Nkuna, Oscar**Date:**2017**Subjects:**Graph theory , Graph coloring**Language:**English**Type:**Masters (Thesis)**Identifier:**http://hdl.handle.net/10210/279401 , uj:30004**Description:**M.Sc. (Mathematics) , Abstract: Please refer to full text to view abstract.**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:**

Karakterisering van planêre grafieke

**Authors:**Wilson, Bònita Sintiché**Date:**1995**Subjects:**Graph theory**Language:**Afrikaans**Type:**Masters Thesis**Identifier:**http://hdl.handle.net/10210/21548 , uj:16147**Description:**Abstract: A graph is called planar if it can be represented on the plane without points of intersection of lines. It is clear from the title that this study is concerned with the characterization of such graphs. In Paragraph 1.2 notation and terminology that are needed throughout, are defined. Specialized notation and terminology are defined when needed. Chapter 2 is concerned with the characterization of planar graphs in terms of forbidden subgraphs. In this regard, specific attention is given to a proof of the Theorem of Kuratowski. In Chapter 3 we prove the characterizations of planar graphs in terms of partially ordered sets of Schnyder and Scheinerman. In Chapter 4 a few characterizations of planar graphs (without proof) are presented. These results of planar graphs are used collectively to state a characterization in Paragraph 4.3. , M.A. (Mathematics)**Full Text:**

**Authors:**Wilson, Bònita Sintiché**Date:**1995**Subjects:**Graph theory**Language:**Afrikaans**Type:**Masters Thesis**Identifier:**http://hdl.handle.net/10210/21548 , uj:16147**Description:**Abstract: A graph is called planar if it can be represented on the plane without points of intersection of lines. It is clear from the title that this study is concerned with the characterization of such graphs. In Paragraph 1.2 notation and terminology that are needed throughout, are defined. Specialized notation and terminology are defined when needed. Chapter 2 is concerned with the characterization of planar graphs in terms of forbidden subgraphs. In this regard, specific attention is given to a proof of the Theorem of Kuratowski. In Chapter 3 we prove the characterizations of planar graphs in terms of partially ordered sets of Schnyder and Scheinerman. In Chapter 4 a few characterizations of planar graphs (without proof) are presented. These results of planar graphs are used collectively to state a characterization in Paragraph 4.3. , M.A. (Mathematics)**Full Text:**

Alternative method for the identification of critical nodes leading to voltage instability in a power system

- Adebayo, Isaiah G., Jimoh, Adisa A., Yusuff, Adedayo A., Sun, Yanxia

**Authors:**Adebayo, Isaiah G. , Jimoh, Adisa A. , Yusuff, Adedayo A. , Sun, Yanxia**Date:**2018**Subjects:**Graph theory , Network topology , Power flow**Language:**English**Type:**Article**Identifier:**http://hdl.handle.net/10210/274893 , uj:29349 , Citation: Adebayo, I.G. et al. 2018. Alternative method for the identification of critical nodes leading to voltage instability in a power system.**Description:**Abstract: Introduction of new operation enhancement technologies plus increasing application of power electronics coupled with the continuous increase in load demand has increased the risk of power networks to voltage instability and susceptibility to voltage collapse. This frequent occurrence of voltage collapse in modern power system has been a growing concern to power system utilities. This paper proposes alternative techniques for the identification of critical nodes that are liable to voltage instability in a power system. The first method is based on the critical mode corresponding to the smallest eigenvalues, while the second technique is based on the centrality measure to identify the influential node of the networks. The eigenvector centrality measure is formulated from the response matrices of both the load and generator nodes of the networks. The effectiveness of the suggested approaches is tested using the IEEE 30 bus and the Southern Indian 10 bus power networks. The results are compared to the techniques based on the traditional power flow. The whole procedure of the results involved in the identification of critical nodes through the proposed methods is totally non-iterative and thereby save time and require less computational burden.**Full Text:**

**Authors:**Adebayo, Isaiah G. , Jimoh, Adisa A. , Yusuff, Adedayo A. , Sun, Yanxia**Date:**2018**Subjects:**Graph theory , Network topology , Power flow**Language:**English**Type:**Article**Identifier:**http://hdl.handle.net/10210/274893 , uj:29349 , Citation: Adebayo, I.G. et al. 2018. Alternative method for the identification of critical nodes leading to voltage instability in a power system.**Description:**Abstract: Introduction of new operation enhancement technologies plus increasing application of power electronics coupled with the continuous increase in load demand has increased the risk of power networks to voltage instability and susceptibility to voltage collapse. This frequent occurrence of voltage collapse in modern power system has been a growing concern to power system utilities. This paper proposes alternative techniques for the identification of critical nodes that are liable to voltage instability in a power system. The first method is based on the critical mode corresponding to the smallest eigenvalues, while the second technique is based on the centrality measure to identify the influential node of the networks. The eigenvector centrality measure is formulated from the response matrices of both the load and generator nodes of the networks. The effectiveness of the suggested approaches is tested using the IEEE 30 bus and the Southern Indian 10 bus power networks. The results are compared to the techniques based on the traditional power flow. The whole procedure of the results involved in the identification of critical nodes through the proposed methods is totally non-iterative and thereby save time and require less computational burden.**Full Text:**

Markov chains : a graph theoretical approach

**Authors:**Marcon, Sinclair Antony**Date:**2013-05-01**Subjects:**Markov processes , Graph theory**Type:**Thesis**Identifier:**uj:7506 , http://hdl.handle.net/10210/8363**Description:**M.Sc. (Mathematics) , In chapter 1, we give the reader some background concerning digraphs that are used in the discussion of Markov chains; namely, their Markov digraphs. Warshall’s Algorithm for reachability is also introduced as this is used to define terms such as transient states and irreducibility. Some initial theory and definitions concerning Markov chains and their corresponding Markov digraphs are given in chapter 2. Furthermore, we discuss l–step transitions (walks of length l) for homogeneous and inhomogeneous Markov chains and other generalizations. In chapter 3, we define terms such as communication, intercommunication, recurrence and transience. We also prove some results regarding the irreducibility of some Markov chains through the use of the reachability matrix. Furthermore, periodicity and aperiodicity are also investigated and the existence of walks of any length greater than some specified integer N is also considered. A discussion on random walks on an undirected torus is also contained in this chapter. In chapter 4, we explore stationary distributions and what it means for a Markov chain to be reversible. Furthermore, the hitting time and the mean hitting time in a Markov digraph are also defined and the proof of the theorems regarding them are done. The demonstrations of the theorems concerning the existence and uniqueness of stationary distributions and the Markov Chain Convergence Theorem are carried out. Later in this chapter, we define the Markov digraph of undirected graphs, which are Markov chains as well. The existing theory is then applied to these. In chapter 5, we explore and see how to simulate Markov chains on a computer by using Markov Chain Monte Carlo Methods. We also show how these apply to random q–colourings of undirected graphs. Finally, in chapter 6, we consider a physical application of these Graph Theoretical concepts—the simulation of the Ising model. Initially, the relevant concepts of the Potts model are given and then the Gibbs sampler algorithm in chapter 5 is modified and used to simulate the Ising model. A relation between the chromatic polynomial and the partition function of the Potts model is also demonstrated.**Full Text:**

**Authors:**Marcon, Sinclair Antony**Date:**2013-05-01**Subjects:**Markov processes , Graph theory**Type:**Thesis**Identifier:**uj:7506 , http://hdl.handle.net/10210/8363**Description:**M.Sc. (Mathematics) , In chapter 1, we give the reader some background concerning digraphs that are used in the discussion of Markov chains; namely, their Markov digraphs. Warshall’s Algorithm for reachability is also introduced as this is used to define terms such as transient states and irreducibility. Some initial theory and definitions concerning Markov chains and their corresponding Markov digraphs are given in chapter 2. Furthermore, we discuss l–step transitions (walks of length l) for homogeneous and inhomogeneous Markov chains and other generalizations. In chapter 3, we define terms such as communication, intercommunication, recurrence and transience. We also prove some results regarding the irreducibility of some Markov chains through the use of the reachability matrix. Furthermore, periodicity and aperiodicity are also investigated and the existence of walks of any length greater than some specified integer N is also considered. A discussion on random walks on an undirected torus is also contained in this chapter. In chapter 4, we explore stationary distributions and what it means for a Markov chain to be reversible. Furthermore, the hitting time and the mean hitting time in a Markov digraph are also defined and the proof of the theorems regarding them are done. The demonstrations of the theorems concerning the existence and uniqueness of stationary distributions and the Markov Chain Convergence Theorem are carried out. Later in this chapter, we define the Markov digraph of undirected graphs, which are Markov chains as well. The existing theory is then applied to these. In chapter 5, we explore and see how to simulate Markov chains on a computer by using Markov Chain Monte Carlo Methods. We also show how these apply to random q–colourings of undirected graphs. Finally, in chapter 6, we consider a physical application of these Graph Theoretical concepts—the simulation of the Ising model. Initially, the relevant concepts of the Potts model are given and then the Gibbs sampler algorithm in chapter 5 is modified and used to simulate the Ising model. A relation between the chromatic polynomial and the partition function of the Potts model is also demonstrated.**Full Text:**

Automatically presentable structures

**Authors:**Ras, Charl John**Date:**2012-09-03**Subjects:**Sequential machine theory , Automata , Formal languages , Equivalence relations (Set theory) , Permutation groups , Graph theory , Numbers, Natural , Logic, Symbolic and mathematical**Type:**Thesis**Identifier:**uj:3443 , http://hdl.handle.net/10210/6838**Description:**M.Sc. , In this thesis we study some of the propertie of a clas called automatic structures. Automatic structures are structures that can be encoded (in some defined way) into a set of regular languages. This encoding allows one to prove many interesting properties about automatic structures, including decidabilty results.**Full Text:**

**Authors:**Ras, Charl John**Date:**2012-09-03**Subjects:**Sequential machine theory , Automata , Formal languages , Equivalence relations (Set theory) , Permutation groups , Graph theory , Numbers, Natural , Logic, Symbolic and mathematical**Type:**Thesis**Identifier:**uj:3443 , http://hdl.handle.net/10210/6838**Description:**M.Sc. , In this thesis we study some of the propertie of a clas called automatic structures. Automatic structures are structures that can be encoded (in some defined way) into a set of regular languages. This encoding allows one to prove many interesting properties about automatic structures, including decidabilty results.**Full Text:**

Complexity aspects of certain graphical parameters

**Authors:**Lategan, Frans Adriaan**Date:**2015-10-07**Subjects:**Graph theory , Algorithms**Type:**Thesis**Identifier:**uj:14236 , http://hdl.handle.net/10210/14689**Description:**M.Sc. (Mathematics) , Please refer to full text to view abstract**Full Text:**

**Authors:**Lategan, Frans Adriaan**Date:**2015-10-07**Subjects:**Graph theory , Algorithms**Type:**Thesis**Identifier:**uj:14236 , http://hdl.handle.net/10210/14689**Description:**M.Sc. (Mathematics) , Please refer to full text to view abstract**Full Text:**

Flows in networks : an algorithmic approach

**Authors:**Marcon, Alister Justin**Date:**2013-05-01**Subjects:**Graph theory , Network analysis (Planning) , Algorithms , Mathematical optimization , System analysis**Type:**Thesis**Identifier:**uj:7507 , http://hdl.handle.net/10210/8364**Description:**M.Sc. (Mathematics) , In Chapter 1, we consider the relevant theory pertaining to graphs and digraphs that will be used in the study of flows in networks. Warshall’s algorithm for reachability is also considered since it will allow us to ascertain whether some paths exist in some instance. In Chapter 2, we explore flows and cuts in networks. We define the basic concepts of source, sink, intermediate vertices, capacity, costs and lower-bounds. Feasible flows are defined, as well as the value of a flow. Cuts in capacitated networks are explored and further theory relating the value of a flow and cuts is given. We considered the problem of determining a maximal flow. In particular, we consider augmentations of the flow—this allows us to give a characterization of a maximal flow. The important Max-flow Min-cut theorem is also considered. After having explored the relevant theory, we move on to methods of finding a maximal flow for a given s-t network that has a capacity on each of its arcs. Firstly, we consider zero-one and unit-capacity networks since these play a role in the applications of maximal flows in Chapter 4. We, then, compile the relevant theory and algorithms in order to implement two augmenting path finding algorithms.**Full Text:**

**Authors:**Marcon, Alister Justin**Date:**2013-05-01**Subjects:**Graph theory , Network analysis (Planning) , Algorithms , Mathematical optimization , System analysis**Type:**Thesis**Identifier:**uj:7507 , http://hdl.handle.net/10210/8364**Description:**M.Sc. (Mathematics) , In Chapter 1, we consider the relevant theory pertaining to graphs and digraphs that will be used in the study of flows in networks. Warshall’s algorithm for reachability is also considered since it will allow us to ascertain whether some paths exist in some instance. In Chapter 2, we explore flows and cuts in networks. We define the basic concepts of source, sink, intermediate vertices, capacity, costs and lower-bounds. Feasible flows are defined, as well as the value of a flow. Cuts in capacitated networks are explored and further theory relating the value of a flow and cuts is given. We considered the problem of determining a maximal flow. In particular, we consider augmentations of the flow—this allows us to give a characterization of a maximal flow. The important Max-flow Min-cut theorem is also considered. After having explored the relevant theory, we move on to methods of finding a maximal flow for a given s-t network that has a capacity on each of its arcs. Firstly, we consider zero-one and unit-capacity networks since these play a role in the applications of maximal flows in Chapter 4. We, then, compile the relevant theory and algorithms in order to implement two augmenting path finding algorithms.**Full Text:**

Distance measures in graphs

**Authors:**Osaye, Fadekemi Janet**Date:**2018**Subjects:**Graph theory , Distances - Measurement**Language:**English**Type:**Doctoral (Thesis)**Identifier:**http://hdl.handle.net/10210/292755 , uj:31819**Description:**Abstract: Please refer to full text to view abstract. , Ph.D.**Full Text:**

**Authors:**Osaye, Fadekemi Janet**Date:**2018**Subjects:**Graph theory , Distances - Measurement**Language:**English**Type:**Doctoral (Thesis)**Identifier:**http://hdl.handle.net/10210/292755 , uj:31819**Description:**Abstract: Please refer to full text to view abstract. , Ph.D.**Full Text:**

Generalised colourings of graphs

**Authors:**Frick, Marietjie**Date:**2015-10-07**Subjects:**Representations of graphs , Graph theory**Type:**Thesis**Identifier:**uj:14233 , http://hdl.handle.net/10210/14686**Description:**Ph.D. , Please refer to full text to view abstract**Full Text:**

**Authors:**Frick, Marietjie**Date:**2015-10-07**Subjects:**Representations of graphs , Graph theory**Type:**Thesis**Identifier:**uj:14233 , http://hdl.handle.net/10210/14686**Description:**Ph.D. , Please refer to full text to view abstract**Full Text:**

Minimal reducible bounds, forbidden subgraphs and prime ideals in the lattice of additive hereditary graph properties

**Authors:**Berger, Amelie Julie**Date:**2012-01-24**Subjects:**Graph theory , Lattice theory**Type:**Thesis**Identifier:**uj:1915 , http://hdl.handle.net/10210/4277**Description:**Ph.D. , After giving basic definitions concerning additive hereditary properties of graphs, this document is divided into three main sections, concerning minimal reducible bounds, minimal forbidden subgraphs and prime ideals. We prove that every irreducible property has at least one minimal reducible bound, and that if an irreducible property P is contained in a reducible property R, then there is a minimal reducible bound for P contained in R. In addition we show that every reducible property serves as a minimal reducible bound for some irreducible property. Several applications of these results are given in the case of hom-properties, mainly to show the existence of minimal reducible bounds of certain types. We prove that every degenerate property has a minimal reducible bound where one factor is the class of edgeless graphs and provide evidence that this may also be true for an arbitrary irreducible property. We also consider edge partitions and we show that the results for minimal decomposable bounds are similar to those for minimal reducible bounds. The second set of results deals with minimal forbidden subgraphs of graph properties. We show that every reducible property has infinitely many minimal forbidden subgraphs since the set of all the cyclic blocks making up these graphs is infinite. Finally we consider the lattice of all additive hereditary properies and study the prime ideals in this lattice. We give an example of a prime ideal that is not co-principal and give some requirements that non co-principal prime ideals should satisfy. 'vVe prove that the set of properties with bounded chromatic number is not a prime ideal by showing that a property P with bounded chromatic number can be written as the intersection of two properties with unbounded chromatic number if and only if P contains all trees.**Full Text:**

**Authors:**Berger, Amelie Julie**Date:**2012-01-24**Subjects:**Graph theory , Lattice theory**Type:**Thesis**Identifier:**uj:1915 , http://hdl.handle.net/10210/4277**Description:**Ph.D. , After giving basic definitions concerning additive hereditary properties of graphs, this document is divided into three main sections, concerning minimal reducible bounds, minimal forbidden subgraphs and prime ideals. We prove that every irreducible property has at least one minimal reducible bound, and that if an irreducible property P is contained in a reducible property R, then there is a minimal reducible bound for P contained in R. In addition we show that every reducible property serves as a minimal reducible bound for some irreducible property. Several applications of these results are given in the case of hom-properties, mainly to show the existence of minimal reducible bounds of certain types. We prove that every degenerate property has a minimal reducible bound where one factor is the class of edgeless graphs and provide evidence that this may also be true for an arbitrary irreducible property. We also consider edge partitions and we show that the results for minimal decomposable bounds are similar to those for minimal reducible bounds. The second set of results deals with minimal forbidden subgraphs of graph properties. We show that every reducible property has infinitely many minimal forbidden subgraphs since the set of all the cyclic blocks making up these graphs is infinite. Finally we consider the lattice of all additive hereditary properies and study the prime ideals in this lattice. We give an example of a prime ideal that is not co-principal and give some requirements that non co-principal prime ideals should satisfy. 'vVe prove that the set of properties with bounded chromatic number is not a prime ideal by showing that a property P with bounded chromatic number can be written as the intersection of two properties with unbounded chromatic number if and only if P contains all trees.**Full Text:**

New distance concept and graph theory approach for certain coding techniques design and analysis

- Ouahada, Khmaies, Ferreira, Hendrik C.

**Authors:**Ouahada, Khmaies , Ferreira, Hendrik C.**Date:**2019**Subjects:**Graph theory , Distance mappings , Spectral codes**Language:**English**Type:**Article**Identifier:**http://hdl.handle.net/10210/404135 , uj:33880 , Citation: Ouahada, K. & Ferreira, H.C. 2019. Communications in Applied and Industrial Mathematics, 10(1):1–18. DOI: 10.1515/caim-2019-0XXX**Description:**Abstract: A New graph distance concept introduced for certain coding techniques helped in their design and analysis as in the case of distance-preserving mappings and spectral shaping codes. A graph theoretic construction, mapping binary sequences to permutation sequences and inspired from the k-cube graph has reached the upper bound on the sum of the distances for certain values of the length of the permutation sequence. The new introduced distance concept in the k-cube graph helped better understanding and analyzing for the first time the concept of distance-reducing mappings. A combination of distance and the index-permutation graph concepts helped uncover and verify certain properties of spectral null codes, which were previously difficult to analyze.**Full Text:**

**Authors:**Ouahada, Khmaies , Ferreira, Hendrik C.**Date:**2019**Subjects:**Graph theory , Distance mappings , Spectral codes**Language:**English**Type:**Article**Identifier:**http://hdl.handle.net/10210/404135 , uj:33880 , Citation: Ouahada, K. & Ferreira, H.C. 2019. Communications in Applied and Industrial Mathematics, 10(1):1–18. DOI: 10.1515/caim-2019-0XXX**Description:**Abstract: A New graph distance concept introduced for certain coding techniques helped in their design and analysis as in the case of distance-preserving mappings and spectral shaping codes. A graph theoretic construction, mapping binary sequences to permutation sequences and inspired from the k-cube graph has reached the upper bound on the sum of the distances for certain values of the length of the permutation sequence. The new introduced distance concept in the k-cube graph helped better understanding and analyzing for the first time the concept of distance-reducing mappings. A combination of distance and the index-permutation graph concepts helped uncover and verify certain properties of spectral null codes, which were previously difficult to analyze.**Full Text:**