Lecture: 3 hours
Prerequisite: Graduate standing in Electrical Engineering or Computer Science or consent of instructor
Grading: Letter; two one-hour midterms (50%), final exam (50%)
Fundamental concepts. Vector spaces and graphs. Planar graphs: Whitney’s and Kuratowski’s theorems. Topological parameters: packings and coverings. Connectivity: Menger’s theorem. Hamilton graphs: Posa’s and Chvatal’s theorems. Graph factorization: Tutte’s theorem. Graph coloring: Brooks; and Vizing’s theorems.
Expanded Course Description:
1. B. Bollobas, Graph Theory, Springer-Verlag, 1979.
2. F. Harary, Graph Theory, Addison-Wesley, 1969.
3. C. Berge, Graphs and Hypergraphs, North-Holland and American Elesevier Publishing Companies, 1973.
4. J. A. Bondy and U. S. R. Murty, Graph Theory and Applications, American Elesevier, 1976.
Reference (4) will be used as text with some material taken from (2), (3), and (1).
ABET Category Content:
Engineering Design : 0 units
Engineering Science : 0 units
Instructor: S.L. Hakimi
Prepared by: L. Hakimi (December 1996)
THIS COURSE DOES NOT DUPLICATE ANY EXISTING COURSE
Last revised: 4/97