Research On Star Set Theory And Graph Reconstruction

Spectral graph theory plays an important role in graph theory,which is widely used in quantum chemistry,computer science,communication network and so on.Star complement theory is an important research subject in graph theory.It has many useful applications in the isomorphism problem of graphs and the existence of strongly regular graphs and so on.Using star complement technique to construct the maximal graph with prescribed graphs as star complements for the given eigenvalues,it has always been the focus of the research of star complement theory.In this paper,the maximal graphs with the stars or the complete bipartite graphs as star complements are described.Specifically,the maximal graphs with the star Sm as a star complement for an eigenvalue-2 and the regular graphs with K2,s(s?2)as a star complement for all possible eigenvalues are studied.The main contents of this thesis are as follows:In chapter 1,the research background,related concepts and some basic theories of this thesis are introduced.In chapter 2,some research progress of star complement theory in recent years are summarized,which mainly deals with the following three aspects:the problem of the upper bound of the multiplicity of eigenvalues,that is,the upper bound of the number of the vertices in star set;the problem of constructing the maximal regular graphs with the prescribed graph as a star complement;the problem of constructing the maximal graphs with the connected graph as a star complement for the given sub-large eigenvalue 1.In chapter 3,the maximal graphs with Sm as a star complement for-2 are discussed.Firstly,it is proved that S3,S4,S13,S14,S21,S23 and S30 are the only stars which can be star complements for-2.Secondly,we proceed to identify all good sets U,when H is any of graphs S3,S4,S13,S14,S21,S23,S30.At last,the maximal graphs with S3,S4,S13 and S21 as a star complement for-2 are described.In chapter 4,the regular graphs with K2,s(s?2)as a star complement for an eigenvalue? are discussed.Firstly,we proved that there is not an r-regular graph G with K2,s(s?2)as a star complement for ?=-2.Secondly,the possible types of vertices in X are proved,moreover,the regular graphs with K2,s(s?2)as a star complement for an eigenvalue?(?){-1,-2} are characterized.At last,the regular graphs with K2,s(s?2)as a star complement for an eigenvalue-1 are described.