MM10  Grafteori  FALL 2006 (instructor Bjarne Toft)

MM10 NEWS NO. 12 (November 29, 2006)

This is a graceful labeling of the Petersen graph where the edge numbers 1, 2, 3, ... , 15 are the numerical differences of the vertex labels.

• Definitions and basic properties (West and Sachs)
• The number of labeled trees on n vertices - Cayley's Theorem (West and Sachs)
• The matrix-tree theorem (West and Sachs)
• Minimum spanning trees (Sachs and Stiebitz and the red book I.5)
• The trevelling salesman (the red book I.6)
  

• Take a look at some of the unsolved problems from Graph Coloring Problems (Chapter 12) on edge-colourings, Wiley 1995.
• Prove Cayley's Theorem from the matrix-tree theorem.
• West Exercises 2.1.39, 2.1.40, 2.1.45
• How are Conjectures 2.2.15 and 2.2.16 in West connected?
  
• If time permits: Opgave 1.25, 1.26, 1.27, 1.28. 1.29 i den røde bog.

The lecture on Wednesday Dec. 6, 2-4 PM,         will deal with Chapter I in the Red Book.
The lecture on Wednesday Dec. 13, 2-4 PM,       will deal with Chapter II in the Red Book.
The lecture on Wednesday Dec. 20, 2-4 PM,       will deal with Chapter III in the Red Book.

Tilmeldte til eksamen: Jacob, Nicolai, Mia, Vagn, Thomas, Jens, Lasse, Kirsten, Per. (Annegrethe er IKKE tilmeldt på den officielle liste).