I.The Basic Information of the Course
Course Number: 202012420013
The EnglishName of theCourse：Spectral Graph Theory
The ChineseName of theCourse：谱图理论
In-classHours andAllocation(Total class hours:32, classroom teaching: 28classhours, classroom discussion:4classhours.)
Credit(s):2
Semester:2
AppliedDiscipline(Professional Degree Category)：Mathematics
CourseObjectOriented：Academic Doctor, Academic Master
EvaluationMode:Big Homework
TeachingMethod:Blended Teaching
CourseOpening Department:College of Mathematical Sciences
II.Prerequisite Course
Graph Theory, Advanced Algebra
III. The Objectives and Requirements of the Course
Spectral graphtheory is an important branch ofCombinatorics, which is widely used in complex networks, quantum physics, chemistry, computer science and other fields. Spectral graphtheory mainly focuses on the relationshipamongthe eigenvalues of graphs, graph structure and graph parameters,wherethe graph eigenvalues include eigenvalues oftheadjacency matrix, Laplacianmatrix and distance matrixof graphs. Spectral graphtheory is an important theoretical course for graduate students majoring in mathematics. Through the study of this course, graduate students can fully learn how to use spectral method to study the structural properties of graphs, be familiar with therolesof spectralgraphtheory incharacterizingthe structure and parameters ofgraphs, master the calculation method of graph eigenvalues, understand the applicationsof spectralgraphtheory in practical problems, andlearnthe latest theories and hot issues in this field.This course will establisha theoretical foundation for the follow-up scientific research of postgraduates.
IV. The Content of the Course
This course mainly introduces the basic concepts, basic properties, research methods and applications of spectral graphtheory. The research methods include spectral method,matrix transformation method and generalized inverse method. The application includes the theoretical role of algebraic graph theory in solving graph theory problems and its practical application in complex networks, quantum physics, chemistry and other disciplines. The course is divided into seven chapters, covering the relationship between graphsand matrices, eigenvalue estimation of graph parameters, bounds of spectral radius of graph, Laplacianspectrum of graph, characteristic polynomial of graph, spectral characterization of graph, spectral properties of regular graph and applicationsof graphspectra.
The first chapter of the course introduces the basic concepts and properties of graph theory and matrix theory, which lays the basic knowledge reserve for thenext severalchapters. Focus on thebasic knowledge of spectral graphtheory involving graph theory and matrixtheory. The second chapter introduces the basic concepts and properties of adjacency spectrumof graphs, introduces the relationship between the adjacency eigenvalues and structure parametersof graphs, and explains the bounds of spectral radiusof graphsand the spectral distribution of line graphsthrough class discussion. In Chapter 3, the basic properties of Laplacianeigenvalues of graphs are introduced. The applications of Laplacianeigenvalues in connectivity, spanning tree countingand edge cut are introduced. The fourth chapter introduces the basic properties of the characteristic polynomials of graphs, including the relationship between the coefficients of the characteristic polynomials of graphs and subgraph structure, and the subgraph reduction method forcomputingthe characteristic polynomial of graphs. In Chapter 5, we introduce the basic theory of spectral characterization of graphs, the construction ofcospectralgraphs and the problem of spectraldeterminationof graphs.The sixthChapter introduces the spectral properties of regular graphs, the basic properties of the second largest eigenvalue of regular graphs and the spectral distribution of strongly regular graphs.
The whole teaching content of this course is arranged as follows.
Chapter 1Graphs and matrices
1.1 Basic definitions and properties of graphs
1.2Basic definitions and properties of matrices
Chapter 2Adjacency spectrum of graphs
2.1 Eigenvalues and graph parameters
2.2Spectral radius of graphs
2.3Spectrum of line graphs
Chapter3Laplacian spectrum of graphs
3.1 Algebraic connectivity of graphs
3.2The Matrix-Tree Theorem
3.3 Laplacian eigenvalues and edge cut of graphs
Chapter4Characteristic polynomial of graphs
4.1 Sachs Coefficient Theorem
4.2Reduced formulas
Chapter5Spectral characterizations of graphs
5.1 Cospectral graphs
5.2Graphs determined by spectra
Chapter6Spectrum of regular graphs
Course for Ideological and Political Education: We will teach the development history of domestic spectral graphtheory, inspire students to remember their mission and contribute to the development of the country and society by introducing the arduous exploration of mathematicalpredecessors. This course introduces the following two ideological and political cases in the teaching process.
Case 1:In the 1980s, China was just beginning to reform and open up, and the study of spectralgraphtheory in China was almost blank. At that time, it was still very difficult tocarry out mathematical research, and it was very difficult to read the latest research results. FujiZhang, JiayuShao, BolianLiuand other scholars have overcome many difficulties, and have made a series of high-level original achievements in the research of eigenvalue estimationof graphs, characteristic polynomialof graphs, sign matrix, etc., which makes Chinese scholars have a high degree of recognition in the field of spectralgraphtheory. Through this example, students are encouraged to increase their national self-confidence and strive to explore the frontier of science.
Case 2:When a postman starts from the post office, he has to walk through every street within his jurisdiction and return to the post office at least once. How can he choose a shortest route? This is the Chinese postman problem, named after MeiguGuan, a Chinese mathematician, who first raised the problem in 1962. If the intersection is represented by the vertex and the street is represented by the edge, then the Chinese postman problem is a combinatorial optimization problem on the weighted graph. The naming of Chinese postman problem shows that Chinese scholars have the ability to put forward the original graph theory with their own characteristics. Through this example, students' confidence in scientific research and culture will be enhanced, and they will be encouraged to combine their theoretical knowledge with the actual needs of social production.
V. Reference Books, Reference Literatures, and Reference Materials
A. Text Books, Monographs and References
1. D. Cvetkovic, P. Rowlinson, S. Simic.An Introduction to the Theory of Graph Spectra.Cambridge University Press, 2010.
2. A.E. Brouwer, W.H. Haemers. Spectra of graphs. Springer, 2012.
3.刘木伙，柳泊濂.图谱的极值理论.广东科技出版社，2017.
Outline Writer (Signature):
Leader in charge of teaching at the College (Signature)：
Date：
中文
