Spanning trees : eigenvalues, special numbers, and the tree-cover ratios, asymptotes and areas of graphs.
Loading...
Date
2014
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This dissertation deals with spanning trees associated with graphs. The number
of spanning trees of a graph can be found by considering the eigenvalues of the
Laplacian matrix associated with that graph. Special classes of graphs are also
considered, such as fan and wheel graphs, where their spanning tree numbers are
connected to special numbers, like the Lucas and Fibonacci numbers. We use the
eigenvalues of the complete graph and its associated circulant matrix to create a
unit-trigonometric equation which generates a sequence and diagram similar to
that of the famous Farey sequence. A new ratio is introduced: the tree-cover ratio
involving spanning trees and vertex coverings and is motivated by the fact that
such a ratio, associated with complete graphs, has the asymptotic convergence
identical to that of the secretary problem. We use this ratio to introduce the idea
of tree-cover asymptotes and areas and determine such values for known classes
of graphs. This ratio, in communication networks, allows for the investigation of
the outward social connectivity from a vertex covering to the rest of the network
when a large number of vertices are involved.
Description
M. Sc. University of KwaZulu-Natal, Durban 2014.
Keywords
Spanning trees (Graph theory), Eigenvalues., Laplacian matrices., Theses -- Mathematics.