No description available.

No description available.

No description available.

In a recent manuscript (Stratification and domination in graphs. Discrete Math. 272 (2003), 171-185) a new mathematical framework for studying domination is presented. It is shown that the domination number and many domination related parameters can be interpreted as restricted 2-stratifications or 2-colorings. This framework places the domination number in a new perspective and suggests many other parameters of a graph which are related in some way to the domination number. In this thesis, we continue this study of domination and stratification in graphs. Let F be a 2-stratified graph with one fixed blue vertex v specified. We say that F is rooted at the blue vertex v. An F-coloring of a graph G is a red-blue coloring of the vertices of G such that every blue vertex v of G belongs to a copy of F (not necessarily induced in G) rooted at v. The F-domination number yF(GQ of G is the minimum number of red vertices of G in an F-coloring of G. Chapter 1 is an introduction to the chapters that follow. In Chapter 2, we investigate the X-domination number of prisms when X is a 2-stratified 4-cycle rooted at a blue vertex where a prism is the cartesian product Cn x K2, n > 3, of a cycle Cn and a K2. In Chapter 3 we investigate the F-domination number when (i) F is a 2-stratified path P3 on three vertices rooted at a blue vertex which is an end-vertex of the F3 and is adjacent to a blue vertex and with the remaining vertex colored red. In particular, we show that for a tree of diameter at least three this parameter is at most two-thirds its order and we characterize the trees attaining this bound. (ii) We also investigate the F-domination number when F is a 2-stratified K3 rooted at a blue vertex and with exactly one red vertex. We show that if G is a connected graph of order n in which every edge is in a triangle, then for n sufficiently large this parameter is at most (n — /n)/2 and this bound is sharp. In Chapter 4, we further investigate the F-domination number when F is a 2- stratified path P3 on three vertices rooted at a blue vertex which is an end-vertex of the P3 and is adjacent to a blue vertex with the remaining vertex colored red. We show that for a connected graph of order n with minimum degree at least two this parameter is bounded above by (n —1)/2 with the exception of five graphs (one each of orders four, five and six and two of order eight). For n > 9, we characterize those graphs that achieve the upper bound of (n — l)/2. In Chapter 5, we define an f-coloring of a graph to be a red-blue coloring of the vertices such that every blue vertex is adjacent to a blue vertex and to a red vertex, with the red vertex itself adjacent to some other red vertex. The f-domination number yz{G) of a graph G is the minimum number of red vertices of G in an f-coloring of G. Let G be a connected graph of order n > 4 with minimum degree at least 2. We prove that (i) if G has maximum degree A where A 4 with maximum degree A where A 5 with maximum degree A where 3 / Thesis (Ph.D.)-University of KwaZulu-Natal, Pietermaritzburg, 2006.

This thesis deals with several aspects of planar graphs, and some of the problems associated with non-planar graphs. Chapter 1 is devoted to introducing some of the fundamental notation and tools used in the remainder of the thesis. Graphs serve as useful models of electronic circuits. It is often of interest to know if a given electronic circuit has a layout on the plane so that no two wires cross. In Chapter 2, three efficient algorithms are described for determining whether a given 2-connected graph (which may model such a circuit) is planar. The first planarity testing algorithm uses a path addition approach. Although this algorithm is efficient, it does not have linear complexity. However, the second planarity testing algorithm has linear complexity, and uses a recursive fragment addition technique. The last planarity testing algorithm also has linear complexity, and relies on a relatively new data structure called PQ-trees which have several important applications to planar graphs. This algorithm uses a vertex addition technique. Chapter 3 further develops the idea of modelling an electronic circuit using a graph. Knowing that a given electronic circuit may be placed in the plane with no wires crossing is often insufficient. For example, some electronic circuits often have in excess of 100 000 nodes. Thus, obtaining a description of such a layout is important. In Chapter 3 we study two algorithms for obtaining such a description, both of which rely on the PQ-tree data structure. The first algorithm determines a rotational embedding of a 2-connected graph. Given a rotational embedding of a 2-connected graph, the second algorithm determines if a convex drawing of a graph is possible. If a convex drawing is possible, then we output the convex drawing. In Chapter 4, we concern ourselves with graphs that have failed a planarity test of Chapter 2. This is of particular importance, since complex electronic circuits often do not allow a layout on the plane. We study three different ways of approaching the problem of an electronic circuit modelled on a non-planar graph, all of which use the PQ-tree data structure. We study an algorithm for finding an upper bound on the thickness of a graph, an algorithm for determining the subgraphs of a non-planar graph which are subdivisions of the Kuratowski graphs K5 and K3,3, and lastly we present a new algorithm for finding an upper bound on the genus of a non-planar graph. / Thesis (M.Sc.)-University of Natal, Durban,1990.

For any graph parameter, the removal of a vertex from a graph can increase the parameter, decrease the parameter, or leave the parameter unchanged. This dissertation focuses on the case where the removal of a vertex decreases the parameter for the cases of independent domination and total domination. A graph is said to be independent domination vertex-critical, or i-critical, if the removal of any vertex decreases the independent domination number. Likewise, a graph is said to be total domination vertex-critical if the removal of any vertex decreases the total domination number. Following these notions, a graph is independent domination bicritical, or i-bicritical, if the removal of any two vertices decreases the independent domination number, and a graph is total domination bicritical if the removal of any two vertices decreases the total domination number. Additionally, a graph is called strong independent domination bicritical, or strong i-bicritical, if the removal of any two independent vertices decreases the independent domination number by two. Construction results for i-critical graphs, i-bicritical graphs, strong i-bicritical graphs, total domination critical graphs, and total domination bicritical graphs are studied. Many known constructions are extended to provide necessary and sufficient conditions to build critical and bicritical graphs. New constructions are also presented, with a concentration on i-critical graphs. One particular construction shows that for any graph G, there exists an i-critical, i-bicritical, and strong i-bicritical graph H such that G is an induced subgraph of H. Structural properties of i-critical graphs, i-bicritical graphs, total domination critical graphs, and total domination bicritical graphs are investigated, particularly for the connectedness and edge-connectedness of critical and bicritical graphs. The coalescence construction, which has appeared in earlier literature, constructs a graph with a cut-vertex and this construction is studied in great detail for i-critical graphs, i-bicritical graphs, total domination critical graphs, and total domination bicritical graphs. It is also shown that strong i-bicritical graphs are 2-connected and thus the coalescence construction is not useful in this case. Domination vertex-critical graphs (graphs where the removal of any vertex decreases the domination number) have been studied in the literature. A well-known result gives an upper bound on the diameter of such graphs. Here similar techniques are used to provide upper bounds on the diameter for i-critical graphs, strong i-bicritical graphs, and total domination critical graphs. The upper bound for the diameter of i-critical graphs trivially gives an upper bound for the diameter of i-bicritical graphs. For a graph G, the gamma-graph of G is the graph where the vertex set is the collection of minimum dominating sets of G. Adjacency between two minimum dominating sets in the gamma-graph occurs if from one minimum dominating set a vertex can be removed and replaced with a vertex to arrive at the other minimum dominating set. One can think of adjacency between minimum dominating sets in the gamma-graph as a swap of two vertices between minimum dominating sets. In the single vertex replacement adjacency model these two vertices can be any vertices in the minimum dominating sets, and in the slide adjacency model these two vertices must be adjacent in G. (Hence the gamma-graph obtained from the slide adjacency model is a subgraph of the gamma-graph obtained in the single vertex replacement adjacency model.) Results for both adjacency models are presented concerning the maximum degree, the diameter, and the order of the gamma-graph when G is a tree. / Graduate / 0405 / michaedwards@gmail.com

No description available.

Petri nets are used as models in the study of networks involving information flows. Petri nets have also turned out to be useful in the study of many asynchronous concurrent systems.In this thesis, the notions of deadlocks, traps, and liveness are considered from a graph theoretic viewpointA characterization of minimal deadlocks and traps in Petri nets is obtained. For the complete Petri nets, alternative characterizations of deadlocks and traps are obtained. Necessary and sufficient conditions are obtained for complete Petri nets to be deadlock free. Similar conditions for trap free complete Petri nets are also determined. / Department of Computer Science

Graph theory is a relatively new way of thinking in mathematics. Graphs can model a number of different problems. Graph theory introduces solutions to many problems which human beings have faced since ancient times.A study of graphs will not be complete without an introduction to both theory and algorithms. Invention of the tools for studying graphs is necessary in order to help people learn the theory and execute the algorithms. The study of graphs itself, by nature, needs graphical representation which can give clearer images for a better understanding. A windowing environment is selected as an instrument for developing a device to study graphs because of its friendly Graphical User Interface. / Department of Computer Science

A morph between two drawings of the same graph can be thought of as a continuous deformation between the two given drawings. A morph is linear if every vertex moves along a straight line segment from its initial position to its final position. In this thesis we study algorithms for morphing, in which the morphs are given by sequences of linear morphing steps. In 1944, Cairns proved that it is possible to morph between any two planar drawings of a planar triangulation while preserving planarity during the morph. However this morph may require exponentially many steps. It was not until 2013 that Alamdari et al. proved that the morphing problem for planar triangulations can be solved using polynomially many steps. In 1990 it was shown by Schnyder that using special drawings that we call Schnyder drawings it is possible to draw a planar graph on a O(n)×O(n) grid, and moreover such drawings can be found in O(n) time (here n denotes the number of vertices of the graph). It still remains unknown whether there is an efficient algorithm for morphing in which all drawings are on a polynomially sized grid. In this thesis we give two different new solutions to the morphing problem for planar triangulations. Our first solution gives a strengthening of the result of Alamdari et al. where each step is a unidirectional morph. This also leads to a simpler proof of their result. Our second morphing algorithm finds a planar morph consisting of O(n²) steps between any two Schnyder drawings while remaining in an O(n)×O(n) grid. However, there are drawings of planar triangulations which are not Schnyder drawings, and for these drawings we show that a unidirectional morph consisting of O(n) steps that ends at a Schnyder drawing can be found. We conclude this work by showing that the basic steps from our morphs can be implemented using a Schnyder wood and weight shifts on the set of interior faces.