Research On Some Problems Of Star Complement Technique Of Graphs

Spectral graph theory combines graph with several matrices and studies the structural properties of graph with algebraic parameters such as eigenvalues and eigenvectors of matrix.Spectral graph theory is an important research direction in graph theory.It has been widely used in network optimal design,integrated circuit design and operational research.In spectral graph theory,star complement technique is closely related to the complexity of the isomorphism problem of graphs,the eigenvalue multiplicity of graph's adjacency matrix and the existence of strongly regular graphs.In 1953,Harary put forward the concept of signed graph when studying social networks,that is,to put positive signs or negative signs on the edges of the graph.As a natural extension of graph,signed graph has also been used in many fields such as topological graph theory and geometry.In recent years,Rowlinson,Stanic,Ramezani and other experts of graph theory have started to study star complements of signed graph.Constructing maximal graphs by given star complements and eigenvalues is an important research subject of star complement technique.In this paper,the maximal signed graphs with signed C3 or C5 as star complements for eigenvalue-2 are completely constrcuted by using the reconstruction theory of star complement technique,and the switching equivalence of the maximal signed graphs is studied.This paper also considers the order of the maximal signed graphs with odd cycle as a star complement for eigenvalue-2.In 2020,Rowlinson and other experts of graph theory studied the order of regular graphs with a tree as a star complement.Let G be a connected r-regular graph of order n with a tree of order t as a star complement for an adjacent eigenvalue ?(?)?-1,0},where r>3.Clebsch graph is a strongly regular graph with parameters(16,5,0,2).Rowlinson proved that n?1/2(r+1)t-2,equality holds when G is the Clebsch graph,and he proposed whether Clebsch graph is the only graph when the upper bound is obtained?This paper studies the order of graph G by using a partition technique,and gives a positive response to this problem.