National Center for Mathematics (NCM) and School of Mathematical Sciences (SMS)
are jointly organizing a two week intense course on GRAPH THEORY & APPLICATIONS starting
Monday March 7, 2005. Lectures will be given by Prof. Ioan Tomescu at the SMS (68-B New Muslim Town, Lahore).

Graph theory & applications
by Ioan Tomescu

Outline of the course:

1) Basic definitions. Trees. Cyclomatic and cocyclomatic numbers of a
graph. Kruskal's algorithm for minimum spanning tree.

2) Eulerian and bipartite graphs. Characterization theorems.

3) Planar graphs and convex polyhedra. Euler's formula and the five colour
theorem.

4) Flows in networks. Ford-Fulkerson's theorem and algorithm for integer
capacities. Applications to bipartite graphs.

5) Flows of minimum cost in networks.

6) h-Connected graphs and Menger's theorems.

7) Colouring problems: greedy algorithm, Brook's theorem, chromatic index
of a bipartite graph and applications to Clos networks. Chromatic
polynomials.

8) The spectrum of a graph and the adjacency algebra; Hoffman's theorem
and spectra of regular graphs.Harary's theorem.

References

1) B.Bollobas, Modern graph theory, Springer-Verlag, New York,1998.

2) M.Behzad, G.Chartrand, L.Lesniak-Foster, Graphs & digraphs, Wadsworth,1979.

3) N.Biggs, Algebraic graph theory, Cambridge University Press,1974.

4) R.E.Tarjan, Data structures and network algorithms, SIAM, Philadelphia,1989.

5) I.Tomescu, Problems in combinatorics and graph theory, J.Wiley,New York,1985.

The faculty members as well as the research students who possess the necessary background
to benefit from the this course should submi applications (on a plain paper) along with CV and
research publications to the Director SMS (choudary@cwu.edu). NCM/SMS will provide local
hospitality to the participants of the course coming from outside Lahore. For further information,
please contact 042-9231189.