Study-Unit Description

Study-Unit Description


CODE MAT5414

 
TITLE Spectral Graph Theory

 
UM LEVEL 05 - Postgraduate Modular Diploma or Degree Course

 
MQF LEVEL 7

 
ECTS CREDITS 15

 
DEPARTMENT Mathematics

 
DESCRIPTION Graph matrices and their spectra
- Relations to graph structure, Perron-Frobenius Theorem
- Spectral moments and closed walks, Harary-Sachs formula
- Main eigenvalues and walks in graphs
- Self complementary graphs
- Characteristic polynomials of Subgraphs and Overgraphs
- NEPS, Canonical Double Covering.

Graphs with few distinct eigenvalues
- Strong regularity
- Graphs associated with BIBD Designs
- Distance regular and walk regular graphs

Graph partitions
- Equitable, walk and orbit partitions
- Spectra of Nested Split Graphs

Polynomial reconstruction
- Singular graphs
- The role of line-graphs

Integral Graphs
- Moore graphs
- Regularity Constraints

Applications to graph structure, Fullerenes, Regular Polyhedra

Study-unit Aims:

To expose the student to the eigenvalue and eigenvector techniques in the theory of algebraic graph theory;
To provide the student with the necessary basic tools and training for doing independent research in spectral graph theory.

Learning Outcomes:

1. Knowledge & Understanding:

By the end of the study-unit the student will be able to:
- Master graph theoretical concepts in the light of algebraic representation;
- Recognise established lines of thought related to graph spectra;
- Relate the links among certain graph theoretical concepts and matrices;
- Compare different concepts to deduce new results on graph spectra and their applications.

2. Skills:

By the end of the study-unit the student will be able to:
- Formulate and investigate original problems in the field;
- Write mathematical material confidently, accurately and efficiently, making good use of linear algebra;
- Prepare an accurate and comprehensible synthesis of articles and books in discrete mathematics and algebraic graph theory.

Main Text/s and any supplementary readings:

Recommended Texts

Biggs N.L., Algebraic Graph Theory, Cambridge University Press, 2nd Edition, 1994.
Cvetkovic D., Rowlinson P. and Simic S., n Introduction to the Theory of Graph Spectra, London Mathematical Society Student Texts (No. 75) 2009.
Beineke L.W. and Wilson R.J., Selected Topics in Graph Theory, Academic Press, 1988.
Cvetkovic D., Rowlinson P. and Simic S., Eigenspaces of Graphs, Encyclopaedia of Mathematics and its Applications 66, Cambridge University Press, 1997.
Godsil, C. D., Algebraic combinatorics. Chapman and Hall Mathematics Series. New York: Chapman and Hall, 1993.
Godsil, C. D. and Royle, G., Algebraic graph theory. New York: Springer-Verlag, 2004.

 
ADDITIONAL NOTES Pre-requisite Qualifications: B.Sc. with Mathematics as a main area

Follows from: MAT3410

 
STUDY-UNIT TYPE Lecture and Independent Study

 
METHOD OF ASSESSMENT
Assessment Component/s Assessment Due Sept. Asst Session Weighting
Examination (3 Hours) SEM2 Yes 100%

 
LECTURER/S

 

 
The University makes every effort to ensure that the published Courses Plans, Programmes of Study and Study-Unit information are complete and up-to-date at the time of publication. The University reserves the right to make changes in case errors are detected after publication.
The availability of optional units may be subject to timetabling constraints.
Units not attracting a sufficient number of registrations may be withdrawn without notice.
It should be noted that all the information in the description above applies to study-units available during the academic year 2023/4. It may be subject to change in subsequent years.

https://www.um.edu.mt/course/studyunit