ECTS @ IUE ECTS @ IUE ECTS @ IUE ECTS @ IUE ECTS @ IUE ECTS @ IUE ECTS @ IUE

Syllabus ( MATH 567 )

   Basic information
Course title: Algebraic Graph Theory
Course code: MATH 567
Lecturer: Assoc. Prof. Dr. Roghayeh HAFEZIEH
ECTS credits: 7.5
GTU credits: 0 (3+0+0)
Year, Semester: 1/2, Fall and Spring
Level of course: Second Cycle (Master's)
Type of course: Area Elective
Language of instruction: English
Mode of delivery: Face to face
Pre- and co-requisites: Math 511
Professional practice: No
Purpose of the course: There are two main connections between graph theory and algebra. These arise from two algebraic objects associated with a graph: its adjacency matrix and its automorphism group. In this course, more in particular, we focus on the spectral graph theory that studies the relation between graph properties and the spectrum of the adjacency matrix and the Laplacian matrix.
   Learning outcomes Up

Upon successful completion of this course, students will be able to:

  1. They will learn and use the basic techniques and results in the algebraic graph theory

    Contribution to Program Outcomes

    1. Define and manipulate advanced concepts of Mathematics
    2. Relate mathematics to other disciplines and develop mathematical models for multidisciplinary problems

    Method of assessment

    1. Written exam
    2. Homework assignment
    3. Term paper
  2. Describe the spectrum of a graph

    Contribution to Program Outcomes

    1. Define and manipulate advanced concepts of Mathematics

    Method of assessment

    1. Written exam
    2. Homework assignment
  3. Describe the laplacian spectrum of a graph

    Contribution to Program Outcomes

    1. Define and manipulate advanced concepts of Mathematics

    Method of assessment

    1. Written exam
    2. Homework assignment
   Contents Up
Week 1: preliminary results on linear algebra and graph theory
Week 2: Matrices associated to a graph , The spectrum of a graph
Week 3: The spectrum of some graphs , The complete graph ,The complete bipartite graph
Week 4: The cycle , The path , Line graphs ,Cartesian products
Week 5: Strongly regular graphs , The spectrum of an undirected graph
Week 6: Regular graphs , Spanning trees
Week 7: Characterization by spectra.
Week 8: Co-spectral graphs. Midterm Exam.
Week 9: Structure and one eigenvalue, Star complements
Week 10: Graphs with least TWO eigenvalues , Spectral techniques
Week 11: Spectrum and graph structure, Authomorphisms and eigenspaces
Week 12: Distance regular graphs , Laplacian,
Week 13: Laplacian spectrum, The matrix-tree theorem
Week 14: Algebraic connectivity , Laplacian eigenvalues and graph structure. Expansion. Graph automorphism.
Week 15*: -
Week 16*: Final Exam.
Textbooks and materials: Topics in Algebraic Graph Theory; W. Beineke and R.J. Wilson, 2004.
Recommended readings: • Algebraic Graph Theory; C. Godsil and G. Royle, 2001.
• Algebraic Graph Theory; N. Biggs, 1993.
• Spectra of Graphs; D. Cvetkovic, M. Doob and Sachs, 1995.
  * Between 15th and 16th weeks is there a free week for students to prepare for final exam.
Assessment Up
Method of assessment Week number Weight (%)
Mid-terms: 8 30
Other in-term studies: 0
Project: 14 10
Homework: 3,5,7,9,11,13 10
Quiz: 0
Final exam: 16 50
  Total weight:
(%)
   Workload Up
Activity Duration (Hours per week) Total number of weeks Total hours in term
Courses (Face-to-face teaching): 3 14
Own studies outside class: 4 14
Practice, Recitation: 0 0
Homework: 3 6
Term project: 5 5
Term project presentation: 1 1
Quiz: 0 0
Own study for mid-term exam: 10 2
Mid-term: 3 1
Personal studies for final exam: 10 2
Final exam: 3 1
    Total workload:
    Total ECTS credits:
*
  * ECTS credit is calculated by dividing total workload by 25.
(1 ECTS = 25 work hours)
-->