The Characterization Of Regular Graphs With A Complete Multipartite Graph As A Star Complement

Spectral graph theory plays an important role in graph theory,combinatorial matrix theory and algebraic combinatorial theory,which is widely used in quantum chemistry,com-puter science,communication network and so on.Star complement theory is an important research subject in spectral graph theory.It has important applications in the reconstruction of graphs and the characterization of strongly regular graphs and so on.The research of constructing the maximal graphs with a prescribed graph as a star complement is always the focus of star complement theory.In this paper,the regular graphs with a complete multipartite graph as a star comple-ment are described.Specifically,the regular graphs with the complete multipartite graphK_1,1,...,1,t?=???,s?2?as a star complement for a main eigenvalue and the regular graphs withK_s?s?2?as a star complement for a non-main eigenvalue are completely dert-ermined.Also,the regular graphs with the complete multipartite graph_??s,t?2?as a star complement for a non-main eigenvalue are discussed.The specific contents of this thesis are as follows:In chapter 1,the related research background,basic concepts and some theories of this research subject are introduced.In chapter 2,some research progress on the special graphs as star complements are summarized,which mainly involves the following three aspects:the problem of constructing the maximal graphs with the connected graph as a star complement for the given sub-large eigenvalue 1;the problem of constructing the regular graphs and the maximal graphs with the complete bipartite graph as a star complement;the problem of constructing the regular graphs with the complete tripartite graph as a star complement.In chapter 3,the regular graphs withK_1,1,...,1,t?=???,s?2?as a star complement for a eigenvalue ? are discussed.When ? is a main eigenvalue,we prove that the regular graph isG=K_s+2;Whenis a non-main eigenvalue,the case oft=1 is solved in its entirety for first time,i.e.the regular graphs with complete graphK_s?s?2?as a star complement are completely determined.We proved that the regular graphs with????s,t?2?as a star complement for a non-main eigenvalueis only???under a certain condition and we raise a conjecture for the general case.In chapter 4,the conjecture proposed in chapter 3 is studied.All the regular graphs with K_1,1,1,t?t?2?as a star complement for a non-main eigenvalue are determined and the fact satisfied the conjecture.At last,we present the latest research on the conjecture.We confirm that the conjecture is correct when ?=-t and give the general form of the type of vertex in the star set.