On the spectra and the Laplacian spectra of graphs
No Thumbnail Available
Date
2006
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Throughout all graphs are assumed to be simple. Let A(G) and L(G) denote the adjacency and the Laplacian matrix corresponding to a graph G, respectively. The second smallest eigen- value of L(G) is called the algebraic connectivity of G and is denoted by a(G). A corresponding eigenvector is called a Fiedler vector of G. The study of spectral integral variations in graphs has been a subject of interest in the past few years (see Fan [21, 22, 23], Kirkland [46] and So [65]). We say that the spectral integral variation occurs in one place by adding an edge e 2 G if (i) L(G) and L(G + e) have exactly n-1 eigenvalues in common and (ii) if उ is the other eigenvalue of L(G), then उ+2 is the other eigenvalue of L(G + e). We supply a characterization of connected graphs in which spectral integral variation occurs in one place by adding an edge where the changed eigenvalue is the algebraic connectivity. The results proved for that purpose suggest methods to construct graphs for which such variation occurs and also to construct graphs for which such variation never occurs. An argument showing that such a variation can never occur for the Laplacian spectral radius is supplied. Graphs with integer Laplacian spectrum has been a subject of study for many researchers, see, for example, Grone and Merris [34] and Grone, Merris and Sunder [33]. Probably the most common example is the star on n >= 3 vertices with Laplacian eigenvalues 0, 1 (multiplicity n - 2), and n. The characterization of trees with 1 as a Laplacian eigenvalue is rather difficult. It is known that the star is the only tree with algebraic connectivity 1. We take up the problem of characterizing trees that have 1 as the third smallest Laplacian eigenvalue. ...
Description
Supervisor: Sukanta Pati
Keywords
MATHEMATICS