Browsing by Author "Erwin, David"

Now showing 1 - 5 of 5
  • Thumbnail Image
    Item
    Open Access
    Distances in planar graphs
    (2021) Du Preez, Brandon; Erwin, David
    In graph theory, the degree diameter problem asks for the maximum number of vertices a graph with given maximum degree and diameter can have. The face-degree of a face in plane graph is the length of the shortest closed walk traversing the boundary of the face. A plane graph is ρ-face-degree regular if every face has face-degree ρ. This thesis begins with a literature review outlining the results and methods of papers studying planar graphs, particularly those solving the degree diameter problem for various kinds of ρ-facedegree regular graphs. In this review, we provide a correction to an error in The degree/diameter problem in maximal planar bipartite graphs by Dalf´o, Huemer and Salas. We investigate plane graphs in which the minimum face-degree is large compared to the graph's diameter, obtain a sharp upper bound for minimum face-degree in terms of diameter, and characterise the extremal graphs for this bound. We demonstrate that if a plane graph has sufficiently large minimum face degree, then it has equally large girth. We use this result to characterise planar generalised polygons (bipartite graphs whose girth is twice their diameter), and solve the degree diameter problem for plane graphs with diameter D that are 2D-face-degree regular. We solve the degree diameter problem for 2-connected, 5-face-degree regular graphs of diameter 3, and demonstrate that if the maximum degree of such a graph is sufficiently large, then the graph necessarily has girth 4. We briefly investigate the distance and connectivity properties of maximal planar graphs. We show there are no non-trivial restrictions on the radius and diameter of a maximal planar graph, give an elementary proof of the well known characterisation of minimal separators in maximal planar graphs, characterise non-separating sets of these graphs, and demonstrate that the centre of a maximal planar graph may have arbitrarily many components. We then study centres of planar and maximal planar graphs in greater depth, and characterise maximal planar graphs that are centres of planar graphs. This characterisation depends upon a new concept we introduce, which is a generalisation of eccentricity, called quasi-eccentricity. We conclude with a list of ideas for further research, open questions and conjectures.
  • Thumbnail Image
    Item
    Open Access
    Domination in graphs: Vizing's conjecture
    (2022) Harnaker, Zahraa; Erwin, David
    Vizing's conjecture remains one of the biggest open problems in domination in graph theory today. The conjecture states that the domination number of the Cartesian product of two graphs is at least as large as the product of the domination numbers of the two factor graphs. The aim of this thesis is to study the various approaches implemented by researchers over the years in an attempt to prove (or disprove) Vizing's conjecture. Graph-theoretic definitions and notations used in this paper are presented in Chapter 1, along with several theorems on domination that will be useful throughout this paper. In Chapters 2, 3 and 4, we explore some of the earliest research done in solving Vizing's conjecture. The three methods studied, namely the simple-labelling rule, the one-half argument and fair reception, all involve partitioning the vertex set of one of the factor graphs in some way and then utilising the structure of the Cartesian product to characterise large classes of graphs for which the conjecture is true. Since Vizing's conjecture is unsolved in general, many partial results related to the conjecture have been proven over the years. One such result, the use of which has become quite widespread in the literature, is studied in Chapter 5. This partial result states that the domination number of the Cartesian product of two graphs is at least half the product of the domination numbers of the two factor graphs. We analyse the double projection argument used to prove this result and include more recent improvements of this bound. We then consider other approaches to solving Vizing's conjecture which do not use some vertex-partitioning technique. Chapter 6 deals with proving the conjecture by minimal counterexample and we list a few properties that a possible minimal counterexample to Vizing's conjecture must satisfy. Moreover, we focus on methods of building graphs which satisfy Vizing's conjecture from other graphs in Chapter 7. Finally, Chapter 8 covers several variations of domination and Vizing-like results for each type of domination. In particular, notable results in fractional, graph-, total, integer, paired-, upper and rainbow domination are studied in detail.
  • Thumbnail Image
    Item
    Open Access
    Generalisations of graph broadcasts
    (2016) Faul, Peter; Erwin, David
    Let G be a graph with vertex set V (G) and edge set E(G). A dominating set S of a graph G is a subset of V (G) such that each vertex in V (G) is either in S itself or adjacent to a vertex in S. Domination and its variants have been well studied [11]. One variation introduced by Erwin in [9], involves studying a function f : V (G) → {0, 1, 2, ...} called a broadcast. We say a broadcast is dominating if for each vertex v there exists a vertex u with f(u) ≠ 0 and dG(v, u) ≤ f(u). The cost of a broadcast f is given by ∑v∈V(G) f(v) and we are usually interested in what the minimum cost is over all dominating broadcasts. In a broadcast the cost to dominatate distance k is k. In this thesis we consider two models in which this need not be the case. The one model equips a graph with a cost function. This approach has been considered before in [14]. The other model equips the graph with a scaling function. We find a connection between the two frameworks, which links them in such a way that each framework proves results about the other.
  • Thumbnail Image
    Item
    Open Access
    Hamiltonian cycles in maximal planar graphs and planar triangulations
    (2017) Mofokeng, Tshenolo; Erwin, David
    In this thesis we study planar graphs, in particular, maximal planar graphs and general planar triangulations. In Chapter 1 we present the terminology and notations that will be used throughout the thesis and review some elementary results on graphs that we shall need. In Chapter 2 we study the fundamentals of planarity, since it is the cornerstone of this thesis. We begin with the famous Euler's Formula which will be used in many of our results. Then we discuss another famous theorem in graph theory, the Four Colour Theorem. Lastly, we discuss Kuratowski's Theorem, which gives a characterization of planar graphs. In Chapter 3 we discuss general properties of a maximal planar graph, G particularly concerning connectivity. First we discuss maximal planar graphs with minimum degree i, for i = 3; 4; 5, and the subgraph induced by the vertices of G with the same degree. Finally we discuss the connectivity of G, a maximal planar graph with minimum degree i. Chapter 4 will be devoted to Hamiltonian cycles in maximal planar graphs. We discuss the existence of Hamiltonian cycles in maximal planar graphs. Whitney proved that any maximal planar graph without a separating triangle is Hamiltonian, where a separating triangle is a triangle such that its removal disconnects the graph. Chen then extended Whitney's results and allowed for one separating triangle and showed that the graph is still Hamiltonian. Helden also extended Chen's result and allowed for two separating triangles and showed that the graph is still Hamiltonian. G. Helden and O. Vieten went further and allowed for three separating triangles and showed that the graph is still Hamiltonian. In the second section we discuss the question by Hakimi and Schmeichel: what is the number of cycles of length p that a maximal planar graph on n vertices could have in terms of n? Then in the last section we discuss the question by Hakimi, Schmeichel and Thomassen: what is the minimum number of Hamiltonian cycles that a maximal planar graph on n vertices could have, in terms of n? In Chapter 5, we look at general planar triangulations. Note that every maximal planar graph on n ≥ 3 vertices is a planar triangulation. In the first section we discuss general properties of planar triangulations and then end with Hamiltonian cycles in planar triangulations.
  • Thumbnail Image
    Item
    Open Access
    Solutions to the conjugacy search and decision problems in the braid group using finite conjugacy class invariants
    (2022) Erasmus, Sane´; Blackman, Claire; Erwin, David
    For two braids, A, B ∈ Bn, the conjugacy decision problem asks whether another braid X ∈ Bn exists such that X−1 A X = B. If we know A, B ∈ Bn are indeed conjugate, the conjugacy search problem asks us to find a braid Y ∈ Bn such that Y −1 A Y = B. In this dissertation we investigate a number of solutions to the conjugacy search problem and conjugacy decision problem in the braid group, all of which use finite invariant subsets of the conjugacy class. In particular, we study the summit set, the super summit set, the improved super summit set algorithm which utilises minimal simple elements, the ultra summit set, improvements to the ultra summit set solution using graph theory, and lastly the set of sliding circuits. As part of this investigation, we also study normal forms of braids, partial orders on the braid group, and the Garside group which generalises the braid group.