ETD Collection

Permanent URI for this collectionhttps://wiredspace.wits.ac.za/handle/10539/104


Please note: Digitised content is made available at the best possible quality range, taking into consideration file size and the condition of the original item. These restrictions may sometimes affect the quality of the final published item. For queries regarding content of ETD collection please contact IR specialists by email : IR specialists or Tel : 011 717 4652 / 1954

Follow the link below for important information about Electronic Theses and Dissertations (ETD)

Library Guide about ETD

Browse

Subject: search.filters.subject.Graph theory

Search Results

Now showing 1 - 6 of 6
  • No Thumbnail Available
    Item
    A derived graph: triangle graph of a graph
    (2021) Sithole, Elias
    In this dissertation we study a derived graph called the triangle graph of a graph. We start by giving a brief background on derived graphs, followed by some basic definitions in graph theory which are relevant in this work. We then discuss some well known classes of graphs and some well known graph operations. Thereafter, we give a known formal definition of a line graph, followed by a few examples and some well known results on line graphs. This leads to the introduction of the main structure of this work, the triangle graph of a graph. We define the triangle graph of a graph and clarify the concept with examples. Then we establish a few properties of a triangle graph of a graph, followed by establishing triangle graphs of certain classes of graphs. Finally, we conclude the dissertation by discussing vertex-join of a graph and the relationship between the graph G, and the triangle graph of a vertex-join of G.
  • No Thumbnail Available
    Item
    Convex optimization for rank-sparsity decomposition, with application to the planted quasi-clique problem
    (2020) Abdulsalaam, Sakirudeen A
    We consider the rank-sparsity decomposition problem with its application to the planted quasi-clique recovery in this thesis. Given a matrix which is a superposition of a low rank and a sparse matrix, the rank sparsity decomposition problem answers the question, “when is it possible to decompose the matrix into its low rank and sparse components?”. The common convex formulation for this problem is to minimize a weighted combination of the nuclear norm and thel1-norm. To prove optimality of solutions with this formulation, it is customary to derive a bound on the dual matrix which certifies the optimality of the solution. Among the methodological contributions of this thesis is the sharp theoretical bounds obtained for the dual matrix. We have improved the results on low rank matrix decomposition by deriving the bound on our dual matrix, using the matrix l∞,2 norm. Moreover, we established conditions under which recovery is achievable by deriving a dual matrix, certifying the optimality of our solution. We adapt the convex formulation for the rank-sparstity decomposition to the planted quasi-clique problem. This problem is a generalization of the planted clique problem which is known to be NP-hard. This problem has applications in areas such as com-munity detection, data mining, bioinformatics, and criminal network analysis. We have considered mathematical modelling, theoretical framework, and computational aspects of the problem. We showed that the planted quasi-clique can be recovered using con-vex programming. We have achieved this by adapting techniques from low rank matrix decomposition to the planted quasi-clique problem. Our numerical results show that when the input graph contains the desired single large dense subgraph and a moderate number of diversionary vertices and edges, the relaxation is exact. We have shown, numerically, the superiority of our formulation over the only existing Mixed Integer Programming (MIP) formulations. Further, we present a simplified proof to show that quasi-cliques also posses what is known as quasi-hereditary property. This property can be exploited to develop enumerative algorithm for the problem
  • No Thumbnail Available
    Item
    The chromatic polynomials of the q-analogue of certain graph operations
    (2018) Ojarikreh, Onoriode Samuel
    In this dissertation, we start by giving basic definitions in graph theory and some classes of graphs which are relevant in this work. We then introduce the chromatic polynomial of a graph which is the main focus of this dissertation. In addition, we discuss some properties of a graph, and the chromatic polynomials which are relevant to this work. In particular, explicit expression of chromatic polynomials of certain classes of graphs are presented. Certain graph operations and the chromatic polynomials of the resultant graphs are discussed. Finally, we introduce the 2-vertex join of a graph and we study its chromatic polynomial, in particular we give the explicit expression of the flow polynomial of the 2-vertex join of a path Pn.
  • No Thumbnail Available
    Item
    Graphs and graph polynomials
    (2017) Kriel, Christo
    In this work we study the k-defect polynomials of a graph G. The k defect polynomial is a function in λ that gives the number of improper colourings of a graph using λ colours. The k-defect polynomials generate the bad colouring polynomial which is equivalent to the Tutte polynomial, hence their importance in a more general graph theoretic setting. By setting up a one-to-one correspondence between triangular numbers and complete graphs, we use number theoretical methods to study certain characteristics of the k-defect polynomials of complete graphs. Specifically we are able to generate an expression for any k-defect polynomial of a complete graph, determine integer intervals for k on which the k-defect polynomials for complete graphs are equal to zero and also determine a formula to calculate the minimum number of k-defect polynomials that are equal to zero for any complete graph.
  • No Thumbnail Available
    Item
    The chromatic polynomial of a graph
    (2016) Adam, A A
    Firstly we express the chromatic polynomials of some graphs in tree form. We then Study a special product that comes natural and is useful in the calculation of some Chromatic polynomials. Next we use the tree form to study the chromatic polynomial Of a graph obtained from a forest (tree) by "blowing up" or "replacing" the vertices Of the forest (tree) by a graph. Then we give explicit expressions, in terms of induced Subgraphs, for the first five coefficients of the chromatic polynomial of a connected Graph. In the case of higher order graphs we develop some useful computational Techniques to obtain some higher order coefficients. In the process we obtain some Useful combinatorial identities, some of which are new. We discuss in detail the Application of these combinatorial identities to some families of graphs. We also discuss Pairs of graphs that are chromatically equivalent and graph that are chromatically Unique with special emphasis on wheels. In conclusion,
  • No Thumbnail Available
    Item
    New solution approaches for the quadratic assignment problem
    (2012-01-18) Fomeni, Franklin Djeumou
    A vast array of important practical problems, in many di erent elds, can be modelled and solved as quadratic assignment problems (QAP). This includes problems such as university campus layout, forest management, assignment of runners in a relay team, parallel and distributed computing, etc. The QAP is a di cult combinatorial optimization problem and solving QAP instances of size greater than 22 within a reasonable amount of time is still challenging. In this dissertation, we propose two new solution approaches to the QAP, namely, a Branch-and-Bound method and a discrete dynamic convexized method. These two methods use the standard quadratic integer programming formulation of the QAP. We also present a lower bounding technique for the QAP based on an equivalent separable convex quadratic formulation of the QAP. We nally develop two di erent new techniques for nding initial strictly feasible points for the interior point method used in the Branch-and-Bound method. Numerical results are presented showing the robustness of both methods.