Strong Connectivity of Polyhedral Complexes
Peter Greenberg
and Martin Loebl
DOI: 10.1023/A:1022413100969
Abstract
A classical theorem of Robbins states that the edges of a graph may be oriented, in such a way that an oriented path exists between any source and destination, if and only if the graph is both connected and two-connected (it cannot be disconnected by the removal of an edge). In this paper, an algebraic version of Robbins” result becomes a lemma on Hilbert bases for free abelian groups, which is then applied to generalize his theorem to higher dimensional complexes. An application to cycle bases for graphs is given, and various examples are presented.
Pages: 117–125
Keywords: strong connectivity; Hilbert basis; homology
Full Text: PDF
References
1. A. Bjorner, "Homology and shellability," in Matroid Applications, N. White (Ed.), Cambridge University Press, Cambridge, 1992.
2. Ken S. Brown, Buildings, Springer-Verlag, New York, 1989.
3. A. Frank, "Graph connectivity and network flows," a chapter of Handbook of Combinatorics (being prepared).
4. M.A. Frumkin, "An application of modular arithmetic to the construction of algorithms for solving systems of linear equations," Soviet Mathematics (Doklady), 17 (1976), 1165-1168.
5. F.R. Giles and W.R. Pulleyblank, "Total dual integrality and integer polyhedra," Linear Algebra and its Applications 25, (1979) 191-196.
6. J.R. Munkres, Elements of Algebraic Topology, Addison-Wesley Publishing Company, Menlo Park, 1984.
7. C.hSt.J.A. Nash-Williams, "On orientations, connectivity and odd vertex pairings in finite graphs," Canad. J. Math. 12(1960)555-567.
8. H.E. Robbins, "A theorem on graphs with an application to a problem of traffic control," American Math. Monthly 46 (1939), 281-283.
9. A. Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, Chichester, 1986.
10. P.D. Seymour, "Sums of circuits," in Graph Theory and Related Topics, J.A. Bondy and U.S.R. Murty (Eds.), pp. 341-355, Academic Press, New York/Berlin* 1979.
2. Ken S. Brown, Buildings, Springer-Verlag, New York, 1989.
3. A. Frank, "Graph connectivity and network flows," a chapter of Handbook of Combinatorics (being prepared).
4. M.A. Frumkin, "An application of modular arithmetic to the construction of algorithms for solving systems of linear equations," Soviet Mathematics (Doklady), 17 (1976), 1165-1168.
5. F.R. Giles and W.R. Pulleyblank, "Total dual integrality and integer polyhedra," Linear Algebra and its Applications 25, (1979) 191-196.
6. J.R. Munkres, Elements of Algebraic Topology, Addison-Wesley Publishing Company, Menlo Park, 1984.
7. C.hSt.J.A. Nash-Williams, "On orientations, connectivity and odd vertex pairings in finite graphs," Canad. J. Math. 12(1960)555-567.
8. H.E. Robbins, "A theorem on graphs with an application to a problem of traffic control," American Math. Monthly 46 (1939), 281-283.
9. A. Schrijver, Theory of Linear and Integer Programming, John Wiley & Sons, Chichester, 1986.
10. P.D. Seymour, "Sums of circuits," in Graph Theory and Related Topics, J.A. Bondy and U.S.R. Murty (Eds.), pp. 341-355, Academic Press, New York/Berlin* 1979.