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

Filters

2014 - 20182

Settings

Author: search.filters.author.Ncambalala, Thokozani Paxwell

Search Results

Now showing 1 - 2 of 2
  • No Thumbnail Available
    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.
  • No Thumbnail Available
    Item
    Combinatorics of lattice paths
    (2014-09-01) Ncambalala, Thokozani Paxwell
    This dissertation consists of ve chapters which deal with lattice paths such as Dyck paths, skew Dyck paths and generalized Motzkin paths. They never go below the horizontal axis. We derive the generating functions to enumerate lattice paths according to di erent parameters. These parameters include strings of length 2, 3, 4 and r for all r 2 f2; 3; 4; g, area and semi-base, area and semi-length, and semi-base and semi-perimeter. The coe cients in the series expansion of these generating functions give us the number of combinatorial objects we are interested to count. In particular 1. Chapter 1 is an introduction, here we derive some tools that we are going to use in the subsequent Chapters. We rst state the Lagrange inversion formula which is a remarkable tool widely use to extract coe cients in generating functions, then we derive some generating functions for Dyck paths, skew Dyck paths and Motzkin paths. 2. In Chapter 2 we use generating functions to count the number of occurrences of strings in a Dyck path. We rst derive generating functions for strings of length 2, 3, 4 and r for all r 2 f2; 3; 4; g, we then extract the coe cients in the generating functions to get the number of occurrences of strings in the Dyck paths of semi-length n. 3. In Chapter 3, Sections 3.1 and 3.2 we derive generating functions for the relationship between strings of lengths 2 and 3 and the relationship between strings of lengths 3 and 4 respectively. In Section 3.3 we derive generating functions for the low occurrences of the strings of lengths 2, 3 and 4 and lastly Section 3.4 deals with derivations of generating functions for the high occurrences of some strings . 4. Chapter 4, Subsection 4.1.1 deals with the derivation of the generating functions for skew paths according to semi-base and area, we then derive the generating functions according to area. In Subsection 4.1.2, we consider the same as in Section 4.1.1, but here instead of semi-base we use semi-length. The last section 4.2, we use skew paths to enumerate the number of super-diagonal bar graphs according to perimeter. 5. Chapter 5 deals with the derivation of recurrences for the moments of generalized Motzkin paths, in particular we consider those Motzkin paths that never touch the x-axis except at (0,0) and at the end of the path.