課程資訊

ALGEBRAIC GRAPH THEORY

97-1

MATH8701

221 U4020

Ceiba 課程網頁
http://ceiba.ntu.edu.tw/971Algebraic_Graph_T

1. Genearlized polygons and Moore graphs
2. Kneser graphs
3. Matrix Theory
4. Interlacing
5. Strongly regular graphs
6. The Laplacian of a graph

Algebraic graph theory is concerned with the use of algebraic techniques in the study of graphs. The aim is to translate properties of graphs into algebraic properties and then, using the results and methods of algebra, to reduce theorems on graphs. The purpose of this course is to introduce basic notation and tools of algebraic graph theory.

Basic knowledge on linear algebra, such as rank and eigenvalue.

Office Hours

0. Lecture note "Spectra of graphs" by Andries E. Brouwer and Willem H.
Haemers. (Textbook)
1. C. Godsil and G. Royle, Algebraic Graph Theory, Springer, 2001.
2. N. Biggs, Algebraic Graph Theory, Second Edition, Cambridge University
Press, 1993.
3. R. A. Brualdi, Combinatorial Matrix Classes, Cambridge University Press,
2006.
4. R. A. Brualdi and H. J. Ryser, Combinatorial Matrix Theory, Cambridge
Univsersity Press, 1991.
5. P. J. Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge
University Press, 1994.
6. C. D. Godsil, Algebraic Combinatorics, Chapman & Hall, 1993.
7. W. T. Tutte, Graph Theory, Addison-Wesley, 1984.

(僅供參考)

 No. 項目 百分比 說明 1. 期中考 35% 2. 期末考 35% 3. 平時成績及作業 30%

 課程進度
 週次 日期 單元主題 第1週 9/16,9/18 0. Introduction 第2週 9/23,9/25 1. Graph spectrum 第3週 9/30,10/02 1. Graph spectrum 第4週 10/07,10/09 2. Linear algebra 第5週 10/14,10/16 2. Linear algebra 第6週 10/21,10/23 3. Graph spectrum (II) 第7週 10/28,10/30 3. Graph spectrum (II) 第8週 11/04,11/06 4. Substructures 第9週 11/11,11/13 4. Substructures 第10週 11/18,11/20 8. Strongly regular graphs (Midterm on 11/18) 第11週 11/25,11/27 8. Strongly regular graphs 第12週 12/02,12/04 8. Strongly regular graphs 第13週 12/09,12/11 11. Distance regular graphs 第14週 12/16,12/18 Rank of a graph 第15週 12/23,12/25 Minimum rank of a graph 第16週 12/30,1/01 Minimum rank of a graph 第17週 1/06,1/08 Minimum rank of a graph 第18週 1/13,1/15 Final Examination at 18:30 of 14 January