Generalized Balloons and the Chinese Postman Problem in Regular Graphs
by
Suil O
University of Illinois at Urbana-Champaign
Coauthors: Douglas B. West

We previously determined the minimum size of a maximum matching in a connected (2r+1)-regular graph with n vertices; the extremal graphs have cut-edges. In this paper, we prove a lower bound for the minimum size of a maximum matching in a t-edge-connected r-regular graph with n vertices, for t ≥ 2 and r ≥ 4. The bound is sharp infinitely often and improves a recent result of Henning and Yeo. We also study the Chinese Postman Problem, the problem of find a shortest closed walk traversing all edges. In a cubic graph, this is equivalent to finding a smallest spanning subgraph in which all vertices have odd degree. We establish an upper bound in terms of the number of vertices. This bound is sharp infinitely often, achieved by the connected cubic graphs having the smallest maximum matchings

Date received: April 18, 2009