Spectral radii of matrices associated with graphs
Date
2015-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
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.
AFRIKAANSE OPSOMMING : Die spektraalradius van ’n grafiek word gedefinieer as die grootste absolute waarde van die eiewaardes van ’n matriks wat met die grafiek geassosieer word. In hierdie tesis bestudeer ons die spektraalradiusse van die nodusmatriks, die afstandsmatriks en ’n matriks wat aan die afstandsmatrix verwant is, vir eenvoudige grafieke. Vir die nodusmatriks bepaal ons die spektraalradiusse van sommige klasse van grafieke. Ons bewys dat die spektraalradius gebruik kan word om die aantal wandelings of geslote wandelings in ’n grafiek af te skat. Verder gee ons grense vir die spektraalradius in terme van sekere grafiekparameters. Ons wys ook dat die gulsige boom, die Volkmann-boom en die uitgebreide stergrafiek die spektraalradius maksimeer onderskeidelik in die versameling van bome met voorgeskrewe graadry, maksimaalgraad en aantal blare. Ons versamel ook verskillende resultate oor die spektraalradiusse van die afstandsmatrikse van sommige klasse van grafieke. Ons ondersoek ’n matriks wat verwant is aan die afstandsmatriks en ons bewys dat die gulsige boom, die Volkmann-boom en die uitgebreide stergrafiek sy spektraalradius maksimeer, ook onderskeidelik in die versameling van bome met voorgeskrewe graadry, maksimaalgraad en aantal blare.
AFRIKAANSE OPSOMMING : Die spektraalradius van ’n grafiek word gedefinieer as die grootste absolute waarde van die eiewaardes van ’n matriks wat met die grafiek geassosieer word. In hierdie tesis bestudeer ons die spektraalradiusse van die nodusmatriks, die afstandsmatriks en ’n matriks wat aan die afstandsmatrix verwant is, vir eenvoudige grafieke. Vir die nodusmatriks bepaal ons die spektraalradiusse van sommige klasse van grafieke. Ons bewys dat die spektraalradius gebruik kan word om die aantal wandelings of geslote wandelings in ’n grafiek af te skat. Verder gee ons grense vir die spektraalradius in terme van sekere grafiekparameters. Ons wys ook dat die gulsige boom, die Volkmann-boom en die uitgebreide stergrafiek die spektraalradius maksimeer onderskeidelik in die versameling van bome met voorgeskrewe graadry, maksimaalgraad en aantal blare. Ons versamel ook verskillende resultate oor die spektraalradiusse van die afstandsmatrikse van sommige klasse van grafieke. Ons ondersoek ’n matriks wat verwant is aan die afstandsmatriks en ons bewys dat die gulsige boom, die Volkmann-boom en die uitgebreide stergrafiek sy spektraalradius maksimeer, ook onderskeidelik in die versameling van bome met voorgeskrewe graadry, maksimaalgraad en aantal blare.
Description
Thesis (MSc)--Stellenbosch University, 2015
Keywords
Spectral radius, Adjacency Matrix, Distance Matrix, Graphs, Volkmann trees, Greedy trees, Extended star graph