---

Graph Theory I

Three credits. Three hours of lecture per week. Prerequisite: Discrete Mathematics or Permission.

Graph theory in mathematics and science. Different types of graphs. Graph operations and subgraphs. Graph isomorphisms and automorphisms. Counting of graphs of different types. Traveling in a graph (walks, trails, paths, cycles,etc.) Graph components and connected graphs. Efficient algorithms for finding subgraphs of some special type in a graph. Binary relations and graphs. Functions, permutations and graphs. Graph descriptions. Trees and their properties. Efficient algorithms for some problems on trees. Degree functions of graphs and their properties. Criteria for a function to be the degree function of a graph of a certain class. Efficient algorithms for recognition of degree functions for graphs of different types. Spanning trees of a graph, their properties and their enumeration. Relations between the sets of spanning trees, cycles and minimal cuts in a graph. The Prüfer coding of a trees. Bipartite graphs and their properties. An efficient algorithm for recognizing bipartite graphs and finding odd cycles in a graph.

Justification

It is difficult to overestimate the importance of graph theory in contemporary mathematics. Deep and elegant in itself, graph theory contains many wonderful ideas and results which are important in numerous branches of mathematics. Graph theoretic ideas also provide the theoretical basis for important concepts in applied areas such as computer science, operations research, management science, electrical and mechanical engineering, chemistry and biology etc.

Objectives

Click here to obtain course objectives.

Syllabus–Semester II 1998-99

1. Introduction and historical remarks.
   1. Graph theory in mathematics.
   2. Graph theory in the natural and engineering sciences
   3. Graph theory in the social and management sciences.
   4. Graph theory in computer science.
2. Different types of graphs.
   1. Simple graphs.
   2. Edge unlabelled graphs.
   3. Edge labelled graphs.
3. Simple operations on graphs.
   1. Deletion of vertices.
   2. Deletion and contraction of edges.
   3. Subdivision of edges.
   4. The union and intersection of graphs.
   5. Graph products.
   6. Complementary graphs.
4. Graph descriptions.
   1. Adjacency and incidency lists.
   2. Graph matrices.
5. Counting of graphs of different types.
   1. The number of different simple graphs with specified vertex set.
   2. The number of different edge unlabelled graphs.
   3. The number of different edge labelled graphs.
6. Graph isomorphism.
   1. Notions of isomorphism and automorphism for graphs of different types.
   2. Properties of the set of automorphisms of a graph.
   3. Vertex and edge orbits of a graph.
   4. Vertex and edge transitive graphs.
   5. The number of graphs of a given type isomorphic to a given graph.
7. Subgraphs of different types.
   1. Spanning subgraphs.
   2. Vertex and edge induced subgraphs.
   3. Graph minors.
   4. Maximal subgraphs with different properties.
8. Binary relations and their directed graphs (digraphs).
   1. The digraph of an equivalence relation. Equivalence classes.
   2. The digraph of a pre-order order relation.
   3. The order induced by a pre-order.
   4. The directed graph of a function f:A –> B where A is finite and B is a subset of A.
   5. The directed graph of a permutation.
9. Binary relations on graphs.
   1. Walk, trail and path relations on the vertex and edge sets of a graph. Corresponding notions for closed walks, trails and paths.
   2. Components of a graph and the corresponding equivalence relations.
   3. Graph connectivity.
   4. Maximal connected subgraphs of a graph.
10. Special walks.
    1. Euler trails and cycles.
    2. Characterizations of Eulerian graphs and digraphs.
    3. Labyrinth problems.
    4. Hamiltonian paths and cycles.
    5. Shortest and longest paths.
11. Trees and forests.
    1. Various properties and characterizations of a tree.
    2. Some problems on trees and efficient algorithms for these problems.
12. Bipartite graphs.
    1. Properties of bipartite graphs.
    2. Minimal non–bipartite graphs.
    3. Special classes of bipartite graphs (trees, even cycles, etc.).
    4. A good characterization of bipartite graphs.
    5. An efficient algorithm for recognizing bipartite graphs and finding odd cycles in a graph.
13. Block structure.
    1. Edge blocks of graphs and the corresponding equivalence relation.
    2. Properties of edge blocks.
    3. Notion of edge 2–connected graphs.
    4. Maximal edge 2–connected subgraphs in a graph.
    5. Tree structure of a connected graph with respect to its edge blocks.
    6. Disjoint paths and connectivity of graphs (Mengers theorem for 2–connected graphs).
14. Assembling and disassembling of graphs.
    1. Assembly and disassembly theorems for trees, connected, and connected graphs.
    2. Ear–assemblies of 2–connected graphs.
    3. Some applications of ear-assembly.
15. Vertex degrees in a graph.
    1. Degree functions.
    2. Criteria for a degree sequence to be the degree function of a graph of a given type.
    3. Simple graphs with thensame degree function.
    4. The switch operation and switch equivalent graphs.
    5. Graphs uniquely defined by their degree functions.
16. Spanning trees of a graph.
    1. Recursive enumeration of spanning trees.
    2. Prüffer coding of the spanning trees of a complete graph.
    3. Cayley’s formula.

Text

• J.A. Bondy and U.S.R. Murty, Graph Theory With Applications, North Holland, Amsterdam, 1976.

Bibliography

1. D.B. West, Introduction to Graph Theory, Prentice Hall, 1996.
2. M. Behzad, G. Chartrand, and Linda Lesniak–Forest, Graphs and Digraphs, Wadsworth International Group, 1981.

---

Graph Theory II

Three credits. Three hours of lecture per week.
Prerequisite: Graph Theory I.

Objectives

Click here to obtain course objectives.

Syllabus

1. Rapid Review of Graph Theory I.
2. Matchings and coverings in bipartite graphs.
   1. Systems of distinct representatives.
   2. An existance criterion — Hall’s theorem.
   3. Minimum vertex covering of edges and maximum matching — König’s theorem.
3. Ear assemblies for 3-connected graphs
   1. 3-connected graphs.
   2. Topological equivalence of graphs.
   3. Topologically 3-connected graphs.
   4. Essential vertices in a topologically 3-connected graph.
   5. Threads. Deletion of threads.
   6. Topologically induced subgraphs.
   7. Every top 3-connected graph contains Top K_4.
   8. Every top 3-connected graph is the union of the subgraph induced by the essential vertices together with nontrivial threads.
   9. G-admissible paths where G is a topologically 3-connected graph.
   10. Ear assembly of a 3-connected graph.
   11. Ear assemblies which preserve a given vertex set.
4. Graph planarity
   1. Various embeddings of a graph into a plane.
   2. Geometrical duality of graphs.
   3. Euler’s formula.
   4. Minimal non-planar graphs.
   5. Kuratowski’s planarity criterion.
5. Eulerian Graphs
   1. Walks, trails and paths and cycles.
   2. Euler trails and Euler circuits.
   3. Characterizations of Eulerian graphs and digraphs.
   4. Fleury’s algorithm.
   5. Minimum coverings of a graph by Euler trails.
   6. Labyrinth problems.
   7. The arborescence generated by an Euler cycle. van Aaardenne-Ehrenfest, de Bruijn theorem on the mumber of Euler circuits of an Eulerian digraph.
   8. Chinese postman problems.
6. Hamiltonian Graphs
   1. Hamiltonian paths and cycles.
   2. Graph closure.
   3. Sufficient conditions for a hamiltonian cycle.
   4. Chvátal’s [1972] theorem on maximal non hamiltonian graphs.
   5. Dirac’s [1952] theorem on longest cycles.
   6. Claw free graphs
   7. Chvátal conjecture: Every 2-tough graph is hamiltonian.
   8. A closure operation on claw free graphs
   9. Equivalence of the following conjectures in a 4-connected graph.
      1. If $G$ is claw free then $G$ is hamiltoniam.
      2. If $G$ is a line graph then $G$ is hamiltomian.
      3. If $G$ is the line graph of a triangle free graph, then $G$ is hamiltonian.
   10. A 7-connected claw free graph is hamiltonian.

Text

• J.A. Bondy and U.S.R. Murty, Graph Theory With Applications, North Holland, Amsterdam, 1976.

Bibliography

1. D.B. West, Introduction to Graph Theory, Prentice Hall, 1996.
2. B. Bollobás, Extremal Graph Theory, Academic Press, 1978.
3. M. Behzad, G. Chartrand, and Linda Lesniak–Forest, Graphs and Digraphs, Wadsworth International Group, 1981.

Index of Courses