<p>This thesis is a study on the confluence of algebraic structures and graph theory. Its aim is to consider groupoids from factorisations of complete graphs. We are especially interested in the cases where the factors are isomorphic. We analyse the loops obtained from homogeneous factorisations and ask if homogeneity is reflected in the kind of loops that are obtained. In particular, we are interested to see if we obtain either groups or quasi-associative Cayley sets from these loops. November 2008.</p>

The minimum degree spanning tree problem is a widely studied NP-hard variation of the minimum spanning tree problem, and a generalization of the Hamiltonian path problem. Most of the work done on the minimum degree spanning tree problem has been on approximation algorithms, and very little work has been done studying graph classes where this problem may be polynomial time solvable. The Hamiltonian path problem has been widely studied on graph classes, and we use classes with polynomial time results for the Hamiltonian path problem as a starting point for graph class results for the minimum degree spanning tree problem. We show the minimum degree spanning tree problem is polynomial time solvable for chain graphs. We then show this problem is polynomial time solvable on bipartite permutation graphs, and that there exist minimum degree spanning trees of these graphs that are caterpillars, and that have other particular structural properties.

This paper is a compilation of results in combinatorics utilizing the probabilistic method. Below is a brief description of the results highlighted in each chapter. Chapter 1 provides basic definitions, lemmas, and theorems from graph theory, asymptotic analysis, and probability which will be used throughout the paper. Chapter 2 introduces the independent domination number. It is then shown that in the random graph model G(n,p) with probability tending to one, the independent domination number is one of two values. Also, the the number of independent dominating sets of given cardinality is analyzed statistically. Chapter 3 introduces the tree domination number. It is then shown that in the random graph model G(n,p) with probability tending to one, the tree domination number is one of two values. Additional related domination parameters are also discussed. Chapter 4 introduces a generalized rook polynomial first studied by J. Goldman et al. Central and local limit theorems are then proven for certain classes of the generalized rook polynomial. Special cases include known central and local limit theorems for the Stirling numbers of the first and second kind and additionally new limit theorems for the Lah numbers and certain classes of known generalized Stirling numbers. Chapter 5 introduces the Kneser Graph. The exact expected value and variance of the distance between [n] and a vertex chosen uniformly at random is given. An asymptotic formula for the expectation is found.

Magister Scientiae - MSc / This thesis is a study on the confluence of algebraic structures and graph theory. Its aim is to consider groupoids from factorisations of complete graphs. We are especially interested in the cases where the factors are isomorphic. We analyse the loops obtained from homogeneous factorisations and ask if homogeneity is reflected in the kind of loops that are obtained. In particular, we are interested to see if we obtain either groups or quasi-associative Cayley sets from these loops. November 2008. / South Africa

>Magister Scientiae - MSc / The pursuit of graphs which are vertex-transitive and non-Cayley on groups has been ongoing for some time. There has long been evidence to suggest that such graphs are a very rarety in occurrence. Much success has been had in this regard with various approaches being used. The aim of this thesis is to find such a class of graphs. We will take an algebraic approach. We will define Cayley graphs on loops, these loops necessarily not being groups. Specifically, we will define meta-Cayley graphs, which are vertex-transitive by construction. The loops in question are defined as the semi-direct product of groups, one of the groups being Z₂ consistently, the other being in the class of dihedral groups. In order to prove non-Cayleyness on groups, we will need to fully determine the automorphism groups of these graphs. Determining the automorphism groups is at the crux of the matter. Once these groups are determined, we may then apply Sabidussi's theorem. The theorem states that a graph is Cayley on groups if and only if its automorphism group contains a subgroup which acts regularly on its vertex set. / Chemicals Industries Education and Training Authority (CHIETA)

Graphs are mathematical abstractions that are useful for solving many types of problems in computer science. In this dissertation, when we talk of graphs we refer to directed graphs (digraphs), which consist of a set of nodes and a set of edges between the nodes, where each edge has a direction. Numerous implementations of graphs exist in computer science however, there is a need for more systematic and complete categorisation of implementations together with some proof of correctness. Completeness is an issue because other studies only tend to discuss the useful implementations and completely or partially ignore the rest. There is also a need for a treatment of graph representations using triples instead pairs as the base component. In this dissertation, a solution to each of these deficiencies is presented. This dissertation is a taxonomic approach towards a comprehensive treatment of digraph representations. The difficulty of comparing implementations with each other is overcome by a creating a taxonomy of digraph implementations. Taxonomising digraph representations requires a systematic analysis of the two main building blocks of digraphs implementations namely maps and sets. The analysis presented in the first part of the dissertation includes a definition of the abstract data types to represent maps and sets together with a comprehensive and systematic collection of algorithms and data-structures required for the implementations thereof. These algorithms are then written and re-written in a common notation and are examined for any essential com¬ponents, differences, variations and common features. Based on this analysis the maps and sets taxonomies are presented. After the completion of maps and sets implementation foundations the dissertation continues with the main contribution: a systematic collection and implementation of other operators used for the manipulation of the base triple components of digraphs and the derivation of the the final taxonomy of digraphs by integrating the maps and sets implementations with the operators on the sets of triples. With the digraph taxonomy we can finally see relationships between implementations and we also can easily establish their similarities and differences. Furthermore, the taxonomy is also useful for further discussions, analysis and visualisation of the complete implementation topography of digraph implementations. / Dissertation (MSc (Computer Science))--University of Pretoria, 2006. / Computer Science / unrestricted

Regular graphs are graphs in which all vertices have the same degree. Many properties of these graphs are known. Such graphs play an important role in modeling network configurations where equipment limitations impose a restriction on the maximum number of links emanating from a node. These limitations do not enforce strict regularity, and it becomes interesting to investigate nonregular graphs that are in some sense close to regular. This dissertation explores a particular class of almost regular graphs in detail and defines generalizations on this class. A linear-time algorithm for the creation of arbitrarily large graphs of the discussed class is provided, and a polynomial-time algorithm for recognizing graphs in the class is given. Several invariants for the class are discussed. The edge-face chromatic number χef of a plane graph G is the minimum number of colors that must be assigned to the edges and faces of G such that no edge or face of G receives the same color as an edge or face with which it is incident or adjacent. A well-known result for the upper bound of χef exists for graphs with maximum degree Δ ≥ 10. We present a tight upper bound for plane graphs with Δ = 9.

Probabilistic graphical models are currently one of the most commonly used architectures for modelling and reasoning with uncertainty. The most widely used subclass of these models is directed acyclic graphs, also known as Bayesian networks, which are used in a wide range of applications both in research and industry. Directed acyclic graphs do, however, have a major limitation, which is that only asymmetric relationships, namely cause and effect relationships, can be modelled between their variables. A class of probabilistic graphical models that tries to address this shortcoming is chain graphs, which include two types of edges in the models representing both symmetric and asymmetric relationships between the variables. This allows for a wider range of independence models to be modelled and depending on how the second edge is interpreted, we also have different so-called chain graph interpretations. Although chain graphs were first introduced in the late eighties, most research on probabilistic graphical models naturally started in the least complex subclasses, such as directed acyclic graphs and undirected graphs. The field of chain graphs has therefore been relatively dormant. However, due to the maturity of the research field of probabilistic graphical models and the rise of more data-driven approaches to system modelling, chain graphs have recently received renewed interest in research. In this thesis we provide an introduction to chain graphs where we incorporate the progress made in the field. More specifically, we study the three chain graph interpretations that exist in research in terms of their separation criteria, their possible parametrizations and the intuition behind their edges. In addition to this we also compare the expressivity of the interpretations in terms of representable independence models as well as propose new structure learning algorithms to learn chain graph models from data.

We present new approaches to define and analyze geometric graphs. The region-counting distances, introduced by Demaine, Iacono and Langerman, associate to any pair of points (p,q) the number of items of a dataset S contained in a region R(p,q) surrounding (p,q). We define region-counting disks and circles, and study the complexity of these objects. Algorithms to compute epsilon-approximations of region-counting distances and approximations of region-counting circles are presented. We propose a definition of the locality for properties of geometric graphs. We measure the local density of graphs using the region-counting distances between pairs of vertices, and we use this density to define local properties of classes of graphs. We illustrate the locality by introducing the local diameter of geometric graphs: we define it as the upper bound on the size of the shortest path between any pair of vertices, expressed as a function of the density of the graph around those vertices. We determine the local diameter of several well-studied graphs such as the Theta-graph, the Ordered Theta-graph and the Skip List Spanner. We also show that various operations, such as path and point queries using geometric graphs as data structures, have complexities which can be expressed as local properties. A family of proximity graphs, called Empty Region Graphs (ERG) is presented. The vertices of an ERG are points in the plane, and two points are connected if their neighborhood, defined by a region, does not contain any other point. The region defining the neighborhood of two points is a parameter of the graph. This family of graphs includes several known proximity graphs such as Nearest Neighbor Graphs, Beta-Skeletons or Theta-Graphs. We concentrate on ERGs that are invariant under translations, rotations and uniform scaling of the vertices. We give conditions on the region defining an ERG to ensure a number of properties that might be desirable in applications, such as planarity, connectivity, triangle-freeness, cycle-freeness, bipartiteness and bounded degree. These conditions take the form of what we call tight regions: maximal or minimal regions that a region must contain or be contained in to make the graph satisfy a given property. We show that every monotone property has at least one corresponding tight region; we discuss possibilities and limitations of this general model for constructing a graph from a point set. We introduce and analyze sigma-local graphs, based on a definition of locality by Erickson, to illustrate efficient construction algorithm on a subclass of ERGs.

No description available.