On The Largest Eigenvalue Of Signed Graphs And Small Eigenvalues Of Graphs

Spectral graph theory is an important research field in graph theory,which has important theoretical and practical applications in computer network,chemistry,biology and other disciplines.In this thesis,we mainly focus on two problems: one problem is the maximum of the largest eigenvalue of signed graphs,the other is the construction of the graphs with small eigenvalues.Specific arrangements are as follows:In chapter 2,we study the maximum of the largest eigenvalue of signed graphs.In 2021,Kafai et al.studied the maximum of the largest eigenvalue of signed complete graphs whose negative edges induced a unicyclic graph,and determined the extremal graphs that attain the maximal eigenvalue.They left a conjecture: if a signed complete graph whose negative edges induce a cactus graph,the largest eigenvalue attains its maximum when all circles of the cactus graph are three circles,and there is only one common vertex with all remaining negative edges being pendant at it.We confirm the conjecture in this chapter.In addition,we also study the structure of the underlying graph when a signed complete graph has the maximal eigenvalue,and find that some subgraphs cannot appear as induced subgraphs of the underlying graph.For simplicity,we call them forbidden subgraphs.We fully characterize the forbidden subgraphs with five vertices and six vertices,and give another simple proof of Kafai et al.’s conjecture by aid of the forbidden subgraphs.In chapter 3,we study the problem about small eigenvalues.Oboudi proposed the concept of small graphs in 2016.If a graph has non-zero eigenvalues belonging to the interval (-1,1),the graph is called a small graph,and such eigenvalues are small eigenvalues.At the same time,Oboudi proposed an open problem: without using any operation on graphs such as Cartesian product or direct product,for every r≥3introduce an infinite family of r-regular small graphs.We construct a class of small graphs for integers r≥3 by aid of Cayley graphs,and prove the proportion is at least 1/r of small eigenvalues.