### 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:**

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