Undirected distances and the postman-structure of graphs.

*(English)*Zbl 0638.05032We present some properties of the distance function and of shortest paths in \(\pm 1\)-weighted undirected graphs. These extend some basic results e.g. on matchings, on the Chinese postman problem, or on plane multicommodity flows. Furthermore, distances turn out to be efficient tools to generalize the matching-structure of graphs to a structure related to subgraphs having only parity constraints on their degrees, (these are called joins or postman sets), a problem posed by Lovàsz and Plummer. The special cases include the generalization of the matching- structure of graphs to the weighted case.

The main result of the paper is a good characterization (linear in the number of edges), conjectured by A. Frank, of the minimum weights of paths from a fixed vertex of an undirected graph without negative circuits. This result contains the well-known minimax theorems on minimum “odd joins” and maximum packings of “odd cuts” (namely Lovàsz’s theorem on half integer packings and its sharpening by Seymour and later by Frank, Tardos) and strengthens them by constructing a “canonical” maximum packing of odd cuts with favourable properties. This packing of odd cuts turns out then to be characteristic for the structure of minimum odd joins. Using these, a Gallai-Edmonds type structural description of minimum odd joins is worked out. (The generalization of the Kotzig- Lovàsz canonical partition will appear in a forthcoming paper.)

Briefly, distances in \(\pm\)-weighted graphs make possible to treat some properties of matchings themselves in a more compact way, and to generalize them providing new results on some other interesting special cases of \(\pm\)-weighted graphs as well. This technique is worked out in the present paper.

The main result of the paper is a good characterization (linear in the number of edges), conjectured by A. Frank, of the minimum weights of paths from a fixed vertex of an undirected graph without negative circuits. This result contains the well-known minimax theorems on minimum “odd joins” and maximum packings of “odd cuts” (namely Lovàsz’s theorem on half integer packings and its sharpening by Seymour and later by Frank, Tardos) and strengthens them by constructing a “canonical” maximum packing of odd cuts with favourable properties. This packing of odd cuts turns out then to be characteristic for the structure of minimum odd joins. Using these, a Gallai-Edmonds type structural description of minimum odd joins is worked out. (The generalization of the Kotzig- Lovàsz canonical partition will appear in a forthcoming paper.)

Briefly, distances in \(\pm\)-weighted graphs make possible to treat some properties of matchings themselves in a more compact way, and to generalize them providing new results on some other interesting special cases of \(\pm\)-weighted graphs as well. This technique is worked out in the present paper.

Reviewer: A.Sebö

##### MSC:

05C38 | Paths and cycles |

05C35 | Extremal problems in graph theory |

05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |

90B10 | Deterministic network models in operations research |

##### Keywords:

distance function; shortest paths; matchings; Chinese postman problem; good characterization; minimum weights of paths; weighted graphs; distances
PDF
BibTeX
XML
Cite

\textit{A. Sebő}, J. Comb. Theory, Ser. B 49, No. 1, 10--39 (1990; Zbl 0638.05032)

Full Text:
DOI

##### References:

[1] | Barahona, F; Maynard, R; Rammal, R; Uhry, J.P, Morphology of ground states of a two-dimensional frustration model, J. phys. A, 15, 673-679, (1982) |

[2] | Barahona, F, Planar multicommodity flows, MAX cut and the Chinese postman problem, (1987), preprint · Zbl 0747.05067 |

[3] | Berge, C, Sur le couplage maximum d’un graphe, C. R. acad. sci. Paris, 247, 258-259, (1958) · Zbl 0086.16301 |

[4] | Edmonds, J, Paths, trees and flowers, Canad. J. math., 17, 449-467, (1965) · Zbl 0132.20903 |

[5] | Edmonds, J; Johnson, E, Matching: A well solved class of integer linear programs, (), 89-92 |

[6] | Edmonds, J; Johnson, E, Matching, Euler tours and the Chinese postman, Math. programming, 5, 88-124, (1973) · Zbl 0281.90073 |

[7] | Edmonds, J; Lovász, L; Pulleyblank, W.R, Brick decompositions and the matching rank of graphs, Combinatorica, 2, 247-274, (1982) · Zbl 0521.05035 |

[8] | \scA. Frank, private communication. |

[9] | Frank, A; Sebő, A; Tardos, E, Covering directed and odd cuts, Math. programming stud., 22, 99-112, (1984) · Zbl 0556.90060 |

[10] | Gallai, T, Maximale systeme unabhängiger kanten, Mat. kut. int. Közl., 9, 373-395, (1964) · Zbl 0135.42001 |

[11] | Korach, E, Packing of T-cuts and other aspects of dual integrality, () |

[12] | Korach, E; Penn, M, (), Technical report 360 |

[13] | Lawler, E, () |

[14] | Lovász, L, 2-matchings and 2-covers of hypergraphs, Acta math. acad. sci. hungar., 26, 433-444, (1975) · Zbl 0339.05123 |

[15] | Lovász, L, On the structure of factorizable graphs, Acta math. acad. sci. hungar., 23, Nos. 1-2, 179-195, (1972) · Zbl 0247.05156 |

[16] | Lovász, L; Plummer, M.D, On bicritical graphs, (), 1051-1079 · Zbl 0308.05127 |

[17] | Lovász, L; Plummer, M.D, () |

[18] | \scK. Matsumoto, T. Nishizeki, and N. Saito, Planar multicommodity flows, maximum matchings and negative cycles, SIAM J. Comput.\bf15, No. 2. · Zbl 0592.05024 |

[19] | Guan, Mei Gu, Graphic programming using odd or even points, Chinese math., 1, 273-277, (1982) |

[20] | \scA. Sebő, Canonical partition of conservative graphs and applications, in preparation. |

[21] | Sebő, A, A quick proof of Seymour’s theorem on T-joins, Discrete math., 64, 101-103, (1987) · Zbl 0618.05040 |

[22] | Sebő, A, Finding the t-join structure of graphs, Math. programming, 36, 123-134, (1986) · Zbl 0626.90090 |

[23] | Sebő, A, The schrijver-system of odd join polyhedra, Combinatorica, 8, No. 1, 103-116, (1988) · Zbl 0642.90096 |

[24] | Sebő, A, Dual integrality and multicommodity flows, () · Zbl 0695.90041 |

[25] | \scA. Sebő, Packing odd cuts and multicommodity flows, Technical Report, Bonn, 89576-OR. |

[26] | Seymour, P.D, Sums of circuits, () · Zbl 0465.05042 |

[27] | Seymour, P.D, On odd cuts and plane multicommodity flows, (), 178-192, (3) · Zbl 0447.90026 |

[28] | Seymour, P.D, The matroids with the MAX-flow-MIN-cut property, J. combin. theory ser. B, 23, 189-222, (1977) · Zbl 0375.05022 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.