The Construction Of Harmonic Graph

Let G be a simple graph of order n, V (G)={v1,..., vn} be vertex set of G.A(G) is (0,1) adjacency matrix of G, d(G)=(d(v1),..., d(vn))Tis degree sequenceof G. An eigenvalue of G is main if it has an associated eigenvector, the sum of whoseentries is not equal to zero. Clearly, G has exactly one main eigenvalue if and onlyif G is regular. It is a long-standing problem of Cvetokvic′to characterize graphswith exactly k(k≥2) main eigenvalues. From2002, A. Dress and Gutman giventhe concept of harmonic graph from calculating the number of walk in graphs:Graph G is called λ harmonic graph, if there exist a positive integer λ such thatA(G)d(G)=λd(G). And from the point of eigenvalue, a non-regular graph G iscalled λ-harmonic graph if and only if G has exactly two main eigenvalues thatare λ and zero. Presently, the connected harmonic graphs with small number ofcycles have already characterized completely such as harmonic tree, acyclic harmonicgraphs, bicyclic harmonic graphs, tetracyclic harmonic graphs, harmonic graphswith5cylices and harmonic graphs with6cylices.In my paper, we firstly introduce the background and some applications of har-monic graph in the first chapter, then we give the notions, lemma, symbols andgraphs involved in this thesis, and we briefly summarize the research status of char-acterize harmonic graphs.In the second chapter, we firstly introduce the basic notions and necessary op-erations, secondly we briefly introduce the main work of my paper: We have provedthe necessary and sufcient condition of λ-harmonic graphs with two distinctdegrees and we find some methods for reconstructing new λ harmonic graphs,and confirmed its constructor method. At last, we confirmed the construction ofλ harmonic graph with3distinct degrees, and do some additional for harmonicgraphs with6cylices.