[PAST EVENT] The Chinese Postman Problem in Regular Graphs of Odd Degree

March 15, 2013
2pm - 3pm
Jones Hall, Room 301
200 Ukrop Way
Williamsburg, VA 23185Map this location
The Chinese Postman Problem in a multigraph is the problem of finding a shortest closed walk traversing all the edges. In a (2r + 1)-regular graph, the problem is equivalent to finding a smallest spanning subgraph in which all vertices have odd degree.

In 1994, Kotstochka and Tulai established a sharp upper bound for the solution. For a 3-regular (multi-) graph with n vertices, we give a simple proof of the bound. We characterize the graphs where equality holds.

The talk should be accessible to undergraduate students.