Font Size: a A A

On Graphs Determined By Their Spectrum

Posted on:2006-12-19Degree:MasterType:Thesis
Country:ChinaCandidate:X L ShenFull Text:PDF
GTID:2120360155456559Subject:Basic mathematics
Abstract/Summary:PDF Full Text Request
The question " which graphs are determined by their spectra? " goes back for half a century, and originates from chemistry. In 1956, Giinthard and Primas raised the question in a paper that relates the theory of graph spectra to Hucke's theory from chemistry. Another application conies from Fisher in 1966. who considered a question of Kac: " Can one hear the shape of a drum?" He modelled the shape of the drum by a graph. Then the sound of that drum is characterized by the eigenvalues of the graph. Thus Kac's question is essentially ours.Answering the question for adjacency or Laplacian matrices seems out of research. In the past half century, there are many results about the question for regular graphs and some special line graphs. But for non-regular graphs, there are few about it. In this paper, we prove that(1) Zn is determined by its adjacency spectrum as well as the Laplacian spectrum. Furthermore, graphs with largest adjacency eigenvalue less than 2 are determined by their adjacency spectra as well as Laplacian spectra.(2) the disjoint union of graph Z_n1, Z_n2, Z_nk (denoted by Z_n1 +Z_n2 + ... + Z_nk) is determined by its adjacency spectrum, where all the numbers n1,n2,..., n_k are positive integer greater than one: k disjoint union of Z_n is determined by its Laplacian spectrum;(3) starlike trees (including the star) are determined by their Laplacian spectra;(4) comb is determined by its Laplacian spectrum;(5) a kind of molecular graph of alkyl is determined by its Laplacian spectrum;(6) graph W_n and the other two double starlike graphs are not determined by their adjacency spectra, but they are determined by their Laplacian spectra,...
Keywords/Search Tags:adjacency matrix, Laplacian matrix, eigenvalue, adjacency spectrum, Laplacian spectrum, cospectral, star, starlike tree, double star, polygraph
PDF Full Text Request
Related items