W&M Featured Events
This calendar presented by
William & Mary
[PAST EVENT] The Chinese Postman Problem in Regular Graphs of Odd Degree
March 15, 2013
2pm - 3pm
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.
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.