Math 4995 Graph Theory II

Syllabus–Semester I 1999-2000

  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 and 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. 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.
© Copyright