Algebraic graph theory

Lecturer: Dr. E. Andriantiana


This course introduces graph theory by studying basic properties of graphs. For this it covers definition, homomorphism and operations of graphs. The main part of the course consists of studying adjacency matrices of graphs. This involves looking at characteristic polynomial and spectrum of the adjacency matrices and using them for combinatoric purpose. Laplacian matrices of graph will be considered as well. As for adjacency matrices, relations between their characteristic polynomial and spectrum to properties of graphs will also be analysed. Depending on availability of time, spplications of graph theory to chemistry, physics and computer science will be pointed out.

Assumption of prior learning

  • Basic linear algebra and group theory

Possible resources

  • Lecture notes will be provided in electronic version uploaded on RUconnected, and in printed version given in class
  • The course follows the book: Norman Biggs, Algebraic graph theory, Cambridge Mathematical Library, Cambridge University Press, 1993.
  • You are also encouraged to read the following books:
    •  Chris Godsil, Gordon F. Royle, "Algebraic Graph Theory", Graduate Texts in Mathematics, Vol. 207, Springer, 2001.
    • R. Diestel, Graph theory, vol. 173 of Graduate Texts in Mathematics, 3rd ed., Springer-Verlag, Berlin, 2005.

Course Organisation

  • Lectures: This course has two one-period lectures each week. 

  • Tutorials: There is no tutorial session for this course, but there are many exercises included in the lecture notes. You are encouraged to attempt to solve those problems as practice for the tests and examination, and also because those exercises often lead to understanding something that we did not have times to cover during the lecture. You can find more exercises in the books listed as resources above. You are welcome come to my office during student consultation times to discuss any exercises related to the course.

  • Class tests and exam: Two tests and one final exam.

 Contact the lecturer for more detailed course documentation.

Last Modified: Tue, 10 Feb 2015 09:22:05 SAST