Study On The Spectral Characterization Of The Complete Graph By Deleting A Path Or Cycle With Small Length

Graph theory is an important branch of combinatorial mathematics,and also an effective tool to solve discrete mathematics problems.It is a mathematical discipline with a long history of development and has attracted much attention from scholars.Spectral theory of graphs is a hot topic in graph theory.Spectral deterministic theory of graphs is a new field in graph theory,which originated from the chemical problem:which graphs are determined by their spectra?A graph can be determined by its spectrum,that is,all graphs having the same spectrum as the graph are isomorphic to the graph.However,there are not so many known graphs that can be determined by spectrum at present.Therefore,more and more scholars begin to study this topic of spectrum determination.In this paper,we study the problem of determining the adjacency spectrum of the subgraphs obtained by removing the paths whose length is equal to 9 and the circles whose length is less than 10 under complete graphs.According to the characteristics of graphs,the number of closed walks and some properties of the adjacency spectrum,we complete the description of the graph structure by using Matlab for calculation and verification to get the spectrum deterministic results.This article is composed of four chapters.The first chapter mainly introduces the research background,significance and research status.Then it gives the preliminary knowledge,basic concepts and notations needed in this paper.Finally,it briefly introduces the research ideas and main results of this paper.In the second chapter,it mainly introduces some lemmas which were used in this paper.In the third chapter,we study the adjacency spectrum certainty of the subgraph obtained by deleting the path of length 9 from the complete graph,and prove that the graphK_n\P₁₀ is determined by its adjacency spectrum at l=10.In the fourth chapter,we study the adjacency spectrum certainty of the subgraph obtained by deleting a cycle from the complete graph,and prove thatK_n\C _kis determined by its adjacency spectrum at3≤k≤8 and k≠6.At the end of the paper,we give a summary of the whole paper,and look forward to further research on this topic.