Course Overview:
This course is an introduction to the theory of graphs intended for students in mathematics and computer science/engineering students with an interest in theory. We start from basic definitions and examples, but hope to move on quickly and cover a broad range of topics. Some applications and relations to Computer Science will also be discussed. Emphasis will be given to reading, understanding and developing proofs. The student will learn a number of standard and powerful algorithms, as well as demonstrating methodologies in graph techniques. In addition the student will be introduced to the use of graphs in the solution of complex problems. Graph theory has become one of the major tools for the design and analysis of algorithms, as well as the focus of much interest in theoretical computer science.

Lectures:
Lectures include the basics of graph theory, Trees, Connectivity, Euler Tours and Hamilton Cycles, Matching, Edge Colorings, Independent Sets and Cliques; Vertex Colorings and Planar graphs. 

MAIN TEXTBOOKS:

  • Graph  Theory with Applications, First Edition, 1976, by J. A. Bondy and U. S. R. Murty
  • Graph  Theory, First Edition, 2008, by J. A. Bondy and U. S. R. Murty

Class time and Location:
Sunday and Tuesday 10:00–11:30 AM, Room 305

Prerequisites:
General mathematical sophistication; and a solid understanding of Algorithms and Linear Algebra at the undergraduate level.

Grading:

  • Homework – 10%
  • Midterm – 40%
  • Endterm – 50%

Midterm Examination: Sunday, 94/01/30, 10:00-11:30 AM
Final Examination: Monday, 94/03/18, 10:30-12:30  

Questions?
I’ll be having office hours for this course on Sunday and Tuesday 08:30–10:00 AM. If this isn’t convenient, email me at hhaji@sbu.ac.ir or talk to me after class.