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.

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.

Ph.D. (Mathematics) / Please refer to full text to view abstract

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.

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.

No description available.

No description available.

No description available.

No description available.

No description available.