3. Electronic Theses and Dissertations (ETDs) - All submissions

Permanent URI for this communityhttps://wiredspace.wits.ac.za/handle/10539/45

For queries relating to content and technical issues, please contact IR specialists via this email address : openscholarship.library@wits.ac.za, Tel: 011 717 4652 or 011 717 1954

Browse

Search Results

Now showing 1 - 2 of 2
  • Item
    Graphs, compositions, polynomials and applications
    (2018) Ncambalala, Thokozani Paxwell
    In this thesis, we study graph compositions of graphs and two graph polynomials, the k-defect polynomials and the Hosoya polynomials. This study was motivated by the fact that it is known that the number of compositions for certain graphs can be extracted from their k-defect polynomials, for example trees and cycles. We want to investigate if these results can be extended to other classes of graphs, in particular to theta and multibridge graphs. Furthermore we want to investigate if we can mimic these results of k-defect polynomials to Hosoya polynomials of graphs. In particular, investigating if the Hosoya polynomials of graphs can be computed using, similar methods to k-defect polynomials. We start the investigation by improving the upper bound for the number of graph compositions of any graph. Thereafter, we give the exact number of graph composi- tion of theta and 4-bridge graphs. We then nd explicit expressions of the k-defect polynomials of a theta graph via its bad coloring polynomial. Furthermore, we nd explicit expressions for the Hosoya polynomials of multibridge graphs and q-vertex joins of graphs with diameter 1 and 2.
  • Item
    Graphs, graph polynomials with applications to antiprisms
    (2014-07-02) Bukasa, Deborah Kembia
    The n-antiprism graph is not widely studied as a class of graphs in graph theory hence there is not much literature. We begin by de ning the n-antiprism graph and discussing properties, which we prove in the thesis, and which have not been previously presented in graph theory literature. Some of our signi cant results include proving that an n-antiprism is 4-connected, 4-edge connected and has a pathwidth of 4. A highly studied area of graph theory is the chromatic polynomial of graphs. We investigate the chromatic polynomial of the antiprism graph and attempt to nd explicit expressions for the chromatic polynomial of the antiprism graph. We express this chromatic polynomial in several forms to discover the best-suited form. We then explore the Tutte polynomial and search for an explicit expression of the Tutte polynomial of the antiprism graph. Using the relationship between a graph and its dual graph, we provide an iterative expression of the Tutte polynomial of the antiprism graph.
Copyright Ownership Is Guided By The University's

Intellectual Property policy

Students submitting a Thesis or Dissertation must be aware of current copyright issues. Both for the protection of your original work as well as the protection of another's copyrighted work, you should follow all current copyright law.