Browsing by Author "Dadedzi, Kenneth"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Analysis of tree spectra
    (Stellenbosch : Stellenbosch University, 2018-12) Dadedzi, Kenneth; Wagner, Stephan; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Division Mathematics.
    ENGLISH ABSTRACT : We study the set of eigenvalues (spectrum) of the adjacency matrix, Laplacian matrix and the distance matrix of trees. In particular, we focus on the distribution of eigenvalues in the spectra of large random trees. The families of random trees considered in this work are simply generated trees and increasing trees. We prove that attaching several copies (two or more) of a tree H to vertices in a tree T “forces" certain real numbers into the adjacency, Laplacian or distance spectrum of the resulting tree. With this construction of forcing subtrees, we prove that the mean proportion of an eigenvalue α in the spectrum of a large random tree is at least the mean number of occurrences of a specific forcing subtree in the large random tree. This gives us explicit lower bounds on the asymptotic mean multiplicity of eigenvalues for different families of random trees. We prove that the mean proportion of an eigenvalue α in the spectrum of the adjacency matrix and Laplacian matrix of a large simply generated tree can be obtained by solving a system of functional equations. We provide an algorithm to solve this system numerically for a given eigenvalue. For instance, using this algorithm, we show that on average approximately 1.4%, 2.1%, 2.5% and 3.3% of the spectrum of a large pruned binary tree, labelled rooted tree, plane tree and pruned ternary tree respectively consist of the eigenvalue 1. Further, we provide explicit formulas for computing the mean proportion of the eigenvalue 0 in the spectrum of a large simply generated tree. We also study the spectra of recursive trees and binary increasing trees. We show that the distribution of the eigenvalue 0 (and other eigenvalues) in these random trees satisfies a central limit theorem. We also compute the mean and variance of the multiplicity of the eigenvalue 0 in the spectrum of a large recursive tree and binary increasing tree. The final chapter deals with related, but somewhat different questions. Given a rooted tree T with leaves v1, v2, . . . , vn, we define the ancestral matrix C(T) of T to be the n × n matrix for which the entry in the i-th row, j-th column is the level (distance from the root) of the first common ancestor of vi and vj . We study properties of this matrix, in particular regarding its spectrum: we obtain several upper and lower bounds for the eigenvalues in terms of other tree parameters. We also find a combinatorial interpretation for the coefficients of the characteristic polynomial of C(T), and show that for dary trees, a specific value of the characteristic polynomial is independent of the precise shape of the tree.
  • Thumbnail Image
    Item
    Spectral radii of matrices associated with graphs
    (Stellenbosch : Stellenbosch University, 2015-12) Dadedzi, Kenneth; Wagner, Stephan; Stellenbosch University. Faculty of Science. Department Mathematical Sciences (Mathematics)
    ENGLISH ABSTRACT : The spectral radius of a graph is defined as the largest absolute value of the eigenvalues of a matrix associated with the graph. In this thesis, we study the spectral radii of the adjacency matrix, the distance matrix and a matrix related to the distance matrix associated to simple graphs. For the adjacency matrix, we determine the spectral radii of some classes of graphs. We prove that the spectral radius can be used to estimate the number of walks and closed walks in the graph. Furthermore, we present bounds on the spectral radius in terms of some graph parameters. We then proceed to show that the greedy tree, the Volkmann tree and the extended star graph maximise the spectral radius among all trees with prescribed degree sequence, maximum degree and number of leaves respectively. We also collect results on the spectral radii of the distance matrices of some classes of graphs. We investigate a matrix that is related to the distance matrix where we proved that the greedy tree, the Volkmann tree and the extended star graph maximise its spectral radius among all trees with prescribed degree sequence, maximum degree and number of leaves respectively.