Math776 Graph Theory, Fall 2005

Math 776 Graph Theory (I), Fall 2005

Instructor: Prof. Lincoln Lu EMAIL: lu@math.sc.edu Time: M W F 2:30p.m.--3:20p.m. Classroom: LC 310 Office Hours: LC 418B Wednesy 10:30 a.m.-- 12:00 p.m. Friday 10:30 a.m.-- 1:00 p.m. or by appointment.	Reference books: Introduction to Graph Theory, second edition, by Douglas B. West, 2001. Graph Theory with Applications by J. A. Bondy and U. S. R. Murty, 1976. Graph Theory by R. Diestel., 2001. Grading Policy: Homeworks 30% Midterm 35% Final project 35%

The midterm exam is scheduled on Oct. 28. It is an open-book exam and covers upto "matchings". Here is a sample exam.
The due date of homework 3 has been extended to Friday, Oct. 7.
- Problem 6 is a result of Rosa. Reference: A. Rosa, On certain Valuations of the vertices of a graph, Theory of Graphs (Internat. Cymposium, Rome, July 1966), Gordon and Breach, N.Y. and Dunod Paris (1967) 349-355.
- Problem 7 is a result of Maheo. Reference: M. Maheo, Strongly graceful graphs, Discrete Math. 29 (1980) 39-46.
The midterm is scheduled on Oct. 28.
The note-taking schedule is changed for Sandy and Wei-Tian.

Choose any reference book. Please read the corresponding chapter including the following contents:

Week 1-4 Concepts:
- Undirected graphs, complete graphs, adjacent matrix, graph isomorphism, automorphism group, connected component, subgraphs, paths, cycles, trails, walks.
- Bipartite graphs, Konig's theorem, an bipartite test algorithm, basic complexity theory, NP-Complete problems.
- Eulerian Circuits, direction graphs, De Bruijn sequences, De Bruijn graphs, orientation of graphs, tournaments, Landau's theorem.
Week 5-6 concepts
- trees, Cayley's theorem, Prufer codes.
- spanning trees, matrix tree theorem
- distance, diameter, decomposition, graceful labellings,
- weighted graphs, minimum spanning tree, Kruskal's algorithm, all shortest paths, Dijkstra's algorithm,
- Breadth-First-Search algorithm, Depth-First-Search algorithm, binary trees Huffman's Algorithm.
Week 7-8 concepts
- matchings, maximium matchings, augumenting path, Berge's theorem, Hall's matching condition.
Week 9-10 concepts Turan number, Turan theorem, Erdos-Simonovits-Stone theorem, Szemeredi's regularity lemma, Turan numbers for bipartite graphs.

Week 11-12 concepts