Math 4995 Graph Theory I

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.

Miscellaneous Notes

Exercises

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.