Some Studies On The Problem Of Graphs Determined By Their Adjacency Spectrum

The graph spectral theory mainly studies other combinatorial propertyof a graph through spectral characterization (the multiset of eigenvalues) ofsome matrices associated with the graph such as adjacency matrix, Laplacianmatrix, signless Laplacian matrix etc. It is not only a cross feld of graphtheory, combinatorics, matrix theory and algebra theory, but also a branch ofalgebraic graph theory. It also has a wide range of applications in graph theory,physics, quantum chemistry, computer science, internet technology etc. Oneof the famous and difcult problem in graph spectral theory is which graphsare determined by their spectrum (DS for short). This thesis is focus on thisfundamental problem.We frstly introduce the background and some applications of graph spec-trum, then we give the notions, symbols and graphs involved in this thesis.Thirdly we briefy summarize the source, background and frequently used toolsof the DS problem. In addition, we give the formulae for computing the num-ber of closed walks of length6,8for any graph and also correct the equationof NG(7) given by G.R. Omidi. At last we outline the main results of thisthesis.In the second chapter, we study the spectral characterization of∞-graph.By frstly determining the degree sequence of graphs cospectral with∞-graphwe give their rough structures: H(a, b, c, d, e) and D(f, g, h, i). Then accordingto Lemma1.4.4, we enumerate the number of closed walks of length6,8ofgraphs B(r, s)(s≥r>7), H(a, b, c, d, e) and D(f, g, h, i). Based on thesecomputation, we obtain the precise structure of the possible cospectral graphs(see Table2.3). Finally by calculating the characteristic polynomials andother techniques we obtain our main result, i.e.,∞-graph B(r, s)(s≥r>7)is determined by its adjacency spectrum if and only if s=r+2, we also givethe unique cospectral graphs when s=r+2. We fnish the spectral characterization of shape trees Dnin chapter three.On the basis of Woo and Neumaier's result we show that the-shape tree Dnis determined by its adjacency spectrum if and only if n=2k+9(k=0,1,2,...). If n=2k+9then when k is odd the unique cospectral mate of Dnis OQ₃(k+1,1,1,1,1,1, k) while when k=2is even the cospectral mates ofDnare OQ₃(k+1,1,1,1,1,1, k) and OQ₃(1,1,+1,1,1,2+1,).In the fourth chapter we investigate the spectral characterization of Πshapes trees Π(a1, a2, a3, a4, a5). First of all we determine the structure ofgraphs cospectral with Π shape trees. Then by searching through a Matlabprogram, we fnd many cospectral graphs. In order to further our research,we classify the Π shape trees into six classes. In the end we fnd a kind of Πshape trees determined by their spectrum.Owning to professor Guanghui Xu and Jiayu Shao's result, in chapter fvewe completely determine all the connected bipartite graphs with the secondlargest eigenvalue λ₂<1that are determined by their spectrum, and furtherfnd the cospectral mates for those that are not DS. In particular, DS doublestars with the second largest eigenvalue λ₂<1are obtained. As a supplementwe prove that the non-bipartite graphs with girth g4and the second largesteigenvalue λ₂<1are all DS.In the last chapter we study the cubic graphs with maximum number oftriangles. By transforming this problem into a optimization problem we de-termine the structure of these extremal cubic graphs and prove that some ofthese extremal cubic graphs are determined by their spectrum.