Satisfactory grade in MATH 2030.  Some experience in computer algorithms and programming is recommended.

Objectives:

The main objective of this course is to introduce graphs as a powerful modeling tool that can be used to solve practical problems in various fields.  To achieve this goal, the course introduces the main concepts of graph theory, graph representations and the basic classes of graphs.  Several famous graph problems and associated algorithms are also covered.  At the end of this course, the student should be able to apply the abstract concepts of graph theory in modeling and solving non-trivial problems in different fields of study.

Credit Hours:

Three credits.

Audience:

Senior and graduate mathematics and computer science majors and minors.

Contents and Organization:

The course covers the basic definitions and concepts related to classical graph theoretic problems.  The course also covers a number of applications in which graph modelings are known to be useful.

• Introduction and basic definitions.
• Graph representations and graph isomorphism.
• Trees and their special properties and applications.
• Connectivity, Euler tours and Hamiltonian cycles.
• Coverings and matchings.
• Cliques and independent colorings.
• Directed graphs and applications.
• Planar graphs and networks.
• General applications: include linear programming, parallel processing, Chemistry applications, and formal language theory.

The coverage will be primarily through lectures, with homework assignments and reading projects.

Evaluation:

Course grade will be based on exams, homework assignments and individual reading projects.  No student will pass the course without attempting all exams and submitting at least 80% of the homework. Reading projects are required for graduate students and optional for undergraduate students.

• Two one-hour exams (200 pts)
• Quizzes (10-30 pts)
• Homework (140 pts)
• Reading project (50 pts)
• Final exam (150 pts)

• Application of graph theory (graph modeling) in Field X
• How to use graphs to solve scheduling problems
• Advanced graph algorithms
• Graph drawing tools
• Design efficient integrated circuits using graph related concepts
• Hypergraphs
• Planarity testing algorithms
• How to use graph-related concepts to solve routing problems in networks
• Matching and weighted matching in graphs
• Graph partitioning
• Graph operations

Text Books:

• Robin J. Wilson and John J. Watkins, Graphs: An introductory Approach, John Wiley & Sons, 1990.
• Hesham H. Ali and Naveed Sherwani, Introduction to Graph Algorithms, to be published by John Wiley & Sons. (Selected chapters will be available in the library).

• J. A. Bondy and U. S. R. Murty, "Graph Theory with Applications," North Holland, 1985.
• Frank Harary, "Graph Theory," Addison-Wesley, 1972.
• Ronald Gould, "Graph Theory,"  Benjamin/Cummings, 1988.
• Fred S. Roberts, "Discrete Mathematical Models," Prentice-Hall, 1976.
• Fred S. Roberts, " Graph Theory and APplications to Problems of Society," SIAM, 1987.
• Robert E. Tarjan, "Data Structure and Network Algorithms," SIAM, 1983.
• J. A. Bondy and U. S. R. Murty, "Graph Theory and Related Topics," Academic Press, 1979.
• Martin C. Golumbic, "Algorithmic Graph Theory and Perfect Graphs," Academic Press, 1980.