Balloons, Chinese Postman Problem and Cycle Double Cover in Cubic Graphs
O Suil, Douglas B. West · 2009
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, which is the problem of find 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. We establish an upper bound for the solution in terms of the edge-connectivity, the vertex degree, and the number of vertices. The bound is sharp infinitely often.