论文部分内容阅读
This thesis focuses on two problems in spectral graph theory known as graphs with few eigenvalues and spectral characterization of graphs.The first problem is studied with respect to the adjacency matrix,Seidel matrix,generalized adjacency matrix and distance matrix.The second problem is studied for the distance matrix.This thesis is organized as follows:In Chapter 1,we discuss the origin and motivation of few eigenvalues and spectral characterization problems.These problems are discussed in details for different matrices related to graphs.In order to understand their importance,known results in these directions are provided.A short summary of the main results in this thesis is provided.Chapter 2 focuses on defining all the necessary terminologies and concepts.Certain important concepts,such as interlacing and equitable partitions of graphs,are described.We give a slightly more detailed proof of the characterization of graphs with two generalized adjacency eigenvalues,which was essentially shown by Haemers&Omidi.Chapter 3 studies graphs with few main and plain（adjacency）eigenvalues.The first part focuses on graphs with exactly two（adjacency）main eigenvalues.Besides constructing certain infinite families of these graphs,we show that the number of distinct valencies and the diameter for this class of graphs are unbounded.Regular two-graphs i.e.graphs with two distinct（Seidel）eigenvalues are used to show the main results.In the second part,we characterize graphs with r main and s plain（adjacency）eigenvalues,where r + s ≤3.The main result of this part is the characterization of disconnected graphs with two main and two plain（adjacency）eigenvalues.We provide certain infinite families of examples of these graphs.In Chapter 4,we study graphs with three distinct generalized adjacency eigenvalues.The structure of these graphs within a non-trivial regular two-graph is determined.Certain parametric conditions are determined for cones over strongly regular graphs such that they have three distinct generalized adjacency eigenvalues.Several constructions of these graphs are provided.Chapter 5 is dedicated to the distance spectra of connected graphs.Some results are obtained for connected graphs with three distinct distance eigenvalues.For example,we characterize connected graphs with three distinct D-eigenvalues such that the largest is non-integral.The main result shows that the hypercubes are determined by their distance spectra.In Chapter 6,we give several open problems which have arisen from the study in this thesis.