Strong connectivity of polyhedral complexes
Robbins' theorem asserts that a simple graph \(G\) may be oriented in such a way as to be strongly connected iff it is 2-connected. Various generalizations in several directions have been obtained. If graphs \(G\) are taken to be 1-(dimensional polyhedral)-complexes, orientations are sets of orientations for the \(n\)-polyhedra of the complex. Strong connectivity in this case means that for each \((n- 1)\)-cycle \(R\) and each \(n\)-polyhedron \(P\) of the complex there are coefficients \(n^R_p\in \{0, 1, 2,\dots\}\) such that \(R= \sum n^R_p d_n \vec P\) (\(\vec P\) is the orientation of \(P\), and \(d_n\vec P= \sum_{Q\in \partial p} \vec Q\) is the formal sum of oriented polyhedra of the boundary of \(P\) with induced orientation). Then the complex permits an orientation which is strongly connected iff each \((n- 1)\) cycle \(R\) is a (formal) sum \(R= \sum m^R_p d_n \vec P\), with \(m^R_p\) an integer, and for each \(n\)-polyhedron \(Q\), \(O= \sum h^Q_p d_n \vec P\), for a choice of integers \(h^Q_p\) with \(h^Q_p\neq 0\). The technique used in obtaining this result is to recast it as a lemma on Hilbert bases in free abelian groups echoing the proof of Robbins' theorem. The proofs obtained then suggest further avenues for generalizations as indicated by the authors' questions and remarks.
- A Theorem on Graphs, with an Application to a Problem of Traffic Control
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 4102053 (Why is no real title available?)
- scientific article; zbMATH DE number 3728302 (Why is no real title available?)
- scientific article; zbMATH DE number 3545733 (Why is no real title available?)
- scientific article; zbMATH DE number 195193 (Why is no real title available?)
- scientific article; zbMATH DE number 863470 (Why is no real title available?)
- On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
- Total dual integrality and integer polyhedra
This page was built for publication: Strong connectivity of polyhedral complexes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1915156)
