Graphs, compositions, polynomials and applications
No Thumbnail Available
Date
2018
Authors
Ncambalala, Thokozani Paxwell
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
Description
A thesis submitted to the
School of Mathematics
in ful lment of the
requirements for the degree of
Doctor of Philosophy, School of Mathematics. Johannesburg, October 2017.
Keywords
Citation
Ncambalala, Thokozani Paxwell (2018) Graphs, compositions, polynomials and applications, University of the Witwatersrand, Johannesburg, <http://hdl.handle.net/10539/25861>
Ncambalala, Thokozani Paxwell (2017) Graphs, compositions, polynomials and applications, University of the Witwatersrand, Johannesburg, <http://hdl.handle.net/10539/25861>
Ncambalala, Thokozani Paxwell (2017) Graphs, compositions, polynomials and applications, University of the Witwatersrand, Johannesburg, <http://hdl.handle.net/10539/25861>