This thesis is a study of the symmetry of graphs and digraphs by considering certain homogeneous embedding requirements. Chapter 1 is an introduction to the chapters that follow. In Chapter 2 we present a brief survey of the main results and some new results in framing number theory. In Chapter 3, the notions of frames and framing numbers is adapted to digraphs. A digraph D is homogeneously embedded in a digraph H if for each vertex x of D and each vertex y of H, there exists an embedding of D in H as an induced subdigraph with x at y. A digraph F of minimum order in which D can be homogeneously embedded is called a frame of D and the order of F is called the framing number of D. We show that that every digraph has at least one frame and, consequently, that the framing number of a digraph is a well defined concept. Several results involving the framing number of graphs and digraphs then follow. Analogous problems to those considered for graphs are considered for digraphs. In Chapter 4, the notions of edge frames and edge framing numbers are studied. A nonempty graph G is said to be edge homogeneously embedded in a graph H if for each edge e of G and each edge f of H, there is an edge isomorphism between G and a vertex induced subgraph of H which sends e to f. A graph F of minimum size in which G can be edge homogeneously embedded is called an edge frame of G and the size of F is called the edge framing number efr(G) of G. We also say that G is edge framed by F. Several results involving edge frames and edge framing numbers of graphs are presented. For graphs G1 and G2 , the framing number fr(G1 , G2 ) (edge framing number ef r(GI, G2 )) of G1 and G2 is defined as the minimum order (size, respectively) of a graph F such that Gj (i = 1,2) can be homogeneously embedded in F. In Chapter 5 we study edge framing numbers and framing number for pairs of cycles. We also investigate the framing number of pairs of directed cycles. / Thesis (Ph.D.)-University of Natal, Pietermaritzburg, 1996.

In this thesis we investigate bounds on distance measures, namely, Steiner diameter and radius, in terms of other graph parameters. The thesis consists of four chapters. In Chapter 1, we define the most significant terms used throughout the thesis, provide an underlying motivation for our research and give background in relevant results. Let G be a connected graph of order p and S a nonempty set of vertices of G. Then the Steiner distance d(S) of S is the minimum size of a connected subgraph of G whose vertex set contains S. If n is an integer, 2 ≤ n ≤ p, the Steiner n-diameter, diamn(G), of G is the maximum Steiner distance of any n-subset of vertices of G. In Chapter 2, we give a bound on diamn(G) for a graph G in terms of the order of G and the minimum degree of G. Our result implies a bound on the ordinary diameter by Erdös, Pach, Pollack and Tuza. We obtain improved bounds on diamn(G) for K3-free graphs and C4-free graphs. In Chapter 3, we prove that, if G is a 3-connected plane graph of order p and maximum face length l then the radius of G does not exceed p/6 + 5l/6 + 5/6. For constant l, our bound improves on a bound by Harant. Furthermore we extend these results to 4- and 5-connected planar graphs. Finally, we complete our study in Chapter 4 by providing an upper bound on diamn(G) for a maximal planar graph G. / Thesis (Ph.D.)-University of KwaZulu-Natal, Westville, 2011.

In this thesis we investigate how the modification of a graph affects various distance measures. The questions considered arise in the study of how the efficiency of communications networks is affected by the loss of links or nodes. In a graph C, the distance between two vertices is the length of a shortest path between them. The eccentricity of a vertex v is the maximum distance from v to any vertex in C. The radius of C is the minimum eccentricity of a vertex, and the diameter of C is the maximum eccentricity of a vertex. The distance of C is defined as the sum of the distances between all unordered pairs of vertices. We investigate, for each of the parameters radius, diameter and distance of a graph C, the effects on the parameter when a vertex or edge is removed or an edge is added, or C is replaced by a spanning tree in which the parameter is as low as possible. We find the maximum possible change in the parameter due to such modifications. In addition, we consider the cases where the removed vertex or edge is one for which the parameter is minimised after deletion. We also investigate graphs which are critical with respect to the radius or diameter, in any of the following senses: the parameter increases when any edge is deleted, decreases when any edge is added, increases when any vertex is removed, or decreases when any vertex is removed. / Thesis (M.Sc.)-University of Natal, 1996.

This thesis deals with an investigation of the integrity of domination in a.graph, i.e., the extent to which domination properties of a graph are preserved if the graph is altered by the deletion of vertices or edges or by the insertion of new edges. A brief historical introduction and motivation are provided in Chapter 1. Chapter 2 deals with kedge-( domination-)critical graphs, i.e., graphsG such that )'(G) = k and )'(G+e) < k for all e E E(G). We explore fundamental properties of such graphs and their characterization for small values of k. Particular attention is devoted to 3-edge-critical graphs. In Chapter 3, the changes in domination number brought aboutby vertex removal are investigated. \ Parameters )'+'(G) (and "((G)), denoting the smallest number of vertices of G in a set 5 such that )'(G-5) > )'(G) ()'(G -5) < )'(G), respectively), are investigated, as are'k-vertex-critical graphs G (with )'(G) = k and )'(G-v) < k for all v E V(O)). The existence of smallest'domination-forcing sets of vertices of graphs is considered. The bondage number 'Y+'(G), i.e., the smallest number of edges of a graph G in a set F such that )'(G- F) > )'(0), is investigated in Chapter 4, as are associated extremal graphs. Graphs with dominating sets or domination numbers that are insensitive to the removal of an arbitrary edge are considered, with particular reference to such graphs of minimum size. Finally, in Chapter 5, we-discuss n-dominating setsD of a graph G (such that each vertex in G-D is adjacent to at least n vertices in D) and associated parameters. All chapters but the first and fourth contain a listing of unsolved problems and conjectures. / Thesis (M.Sc.)-University of Natal, 1993.

Aspects of the fundamental concept of distance are investigated in this dissertation. Two major topics are discussed; the first considers metrics which give a measure of the extent to which two given graphs are removed from being isomorphic, while the second deals with Steiner distance in graphs which is a generalization of the standard definition of distance in graphs. Chapter 1 is an introduction to the chapters that follow. In Chapter 2, the edge slide and edge rotation distance metrics are defined. The edge slide distance gives a measure of distance between connected graphs of the same order and size, while the edge rotation distance gives a measure of distance between graphs of the same order and size. The edge slide and edge rotation distance graphs for a set S of graphs are defined and investigated. Chapter 3 deals with metrics which yield distances between graphs or certain classes of graphs which utilise the concept of greatest common subgraphs. Then follows a discussion on the effects of certain graph operations on some of the metrics discussed in Chapters 2 and 3. This chapter also considers bounds and relations between the metrics defined in Chapters 2 and 3 as well as a partial ordering of these metrics. Chapter 4 deals with Steiner distance in a graph. The Steiner distance in trees is studied separately from the Steiner distance in graphs in general. The concepts of eccentricity, radius, diameter, centre and periphery are generalised under Steiner distance. This final chapter closes with an algorithm which solves the Steiner problem and a Heuristic which approximates the solution to the Steiner problem. / Thesis (M.Sc.)-University of Natal, 1991.

No description available.

No description available.

Theorem: For any rational x ≥ 1, there exists a fully polynomial randomised approximation scheme for evaluating the Tutte polynomial of dense graphs at the point (x,1).

Leaf-labelled trees are used commonly in computational biology and in other disciplines, to depict the ancestral relationships and present-day similarities between both extant and extinct species. Studying these trees from a mathematical perspective provides a foundation for developing tools and techniques that have practical applications. We begin by examining some quartet problems, namely determining the number of quartets that are required to infer the structure of a particular supertree. The quartet graph is introduced as a tool for tackling quartet problems, and is subsequently used to give new characterisations of compatible, definitive and identifying quartet sets. We then turn to investigating some properties of the subtrees induced by a collection of trees. This is motivated in part by the problem of reconstructing two or more trees simultaneously from their combined collection of subtrees. We also use some ideas drawn from Ramsey theory to show the existence of arbitrarily large common subtrees. Finally, we explore some extremal properties of the metric that is induced by the tree bisection and reconnection operation. This includes finding new (asymptotically) tight upper and lower bounds on both the size of the neighbourhoods in the metric space and on the diameter of the corresponding adjacency graph.

Graduate