𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A generalization of Robacker's theorem

✍ Scribed by S.K. Tipnis; L.E. Trotter Jr.

Publisher
Elsevier Science
Year
1989
Tongue
English
Weight
875 KB
Volume
74
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let 9 be the polyhedron given by 9 = {x E R": Nx=O, a~x~b}, where N is a totally unimodular matrix and a and 6 are any integral vectors. For x E R" let (x)' denote the vector obtained from x by changing all its negative components to zeros. Let x1, . . . , xp be the integral points in 9 and let 9+ be the convex hull of (x1)+, . . . , (x")'. In this paper we derive the blocking polyhedron for {x E Z?"+: Mx 3 1) where the rows of M are integral points in 8*. We also show that the optimum objective function values of the integer programming problem max{ 1 -y: yM s w, y > 0 and integral} and its linear programming relaxation differ by less than one for any nonnegative, integral vector w. As a special case of this result we derive Robacker's theorem which states that for a directed graph with two distinguished nodes s and t, the maximum value of an integral packing of forward edges in (s, t)-cuts into a nonnegative, integral weighting w of the edges is equal to the minimum w-weight of an (s, t)-path.

📜 SIMILAR VOLUMES

A generalization of Turán's theorem
A generalization of Turán's theorem
✍ Benny Sudakov; Tibor Szabó; H. Van Vu 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB

## Abstract In this paper, we obtain an asymptotic generalization of Turán's theorem. We prove that if all the non‐trivial eigenvalues of a __d__‐regular graph __G__ on __n__ vertices are sufficiently small, then the largest __K__~__t__~‐free subgraph of __G__ contains approximately (__t__ − 2)/(__

A generalization of carathéodory's theor
A generalization of carathéodory's theorem
✍ Imre Bárány 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 812 KB

The following theorem is lproved. If the sets VI, . . . , Vn+, CR" and a E fly:: conv Vi, then there exist elements ui E Vi (i = 1, . . . , n + 1) such that a E conv{o,, . . . , un+J. Thii is a generalization of Carathtidory's theorem. By applying this and similar results some open questions are ans

A generalization of Petersen's theorem
A generalization of Petersen's theorem
✍ Michel X. Goemans 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 338 KB

Goemans, M.X., A generalization of Petersen's theorem, Discrete Mathematics 115 (1993) 277-282. Petersen's theorem asserts that any cubic graph with at most 2 cut edges has a perfect matching. We generalize this classical result by showing that any cubic graph G = (V, E) with at most 1 cut edge has