Spectral radii of matrices associated with graphs

Dadedzi, Kenneth (2015-12)

Thesis (MSc)--Stellenbosch University, 2015

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.

Thesis

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/98073
This item appears in the following collections: