Site Map | College of Engineering | UC Davis | MyUCDavis

ECS 225 GRAPH THEORY (3) II

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%)

Catalog Description:
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. Basic concepts: paths, circuits, cuts, trees, chains, Euler graphs, and segs and elementary results. (2 lectures)
  2. Matrix representation. Vector spaces on GF(2) and graphs. (4 lectures)
  3. Kuratowski's characterization of planar graphs. Whitney's duality theory. Euler's polyhedra formula. (3 lectures)
  4. Trees. Cayley's tree formula. Variations (2 lectures)
  5. Topological parameters. Genus, crossings, packings, and coverings. (3 lectures)
  6. Connectivity, Menger's theorem and implications. (3 lectures)
  7. Hamiltonian graphs. Posa's theorem and generalization. (3 lectures)
  8. Graph factorization. Berge's matching theory. Tutte's theorem. (3 lectures)
  9. Graph coloring, Brooks' and Vizing's theorems. Chromotac polynomials. (2 lectures)
  10. Applications. (2 lectures)

References:
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

Back to Course Descriptions