On Four Problems in Graph Theory
Ellis L. Johnson, Sebastiano Mosterts · SIAM Journal on Algebraic and Discrete Methods · 1987
The four problems considered are: the Chinese postman problem, the co-postman problem, the odd cut problem, and the odd circuit problem. Relationships are developed between these problems using results from dual matroids and blocking clutters. Connections with Gomory’s group problem are shown. The notion of representations of these binary group problems on augmented graphs is developed along with a discussion of the class of augmented graphs having the same solution set. After some blocking and duality results, we give forbidden augmented minors for problems of one type (e.g., Chinese postman) to be also a second type of problem (e.g., odd cut). Some results are given on b-regular problems and are used in the forbidden augmented minor characterizations.