Strong connectivity of polyhedral complexes
type: Item
instance of: scholarly article
title: Strong connectivity of polyhedral complexes
zbMATH Open document ID: 0852.05058
DOI: 10.1023/A:1022413100969
author: Peter Greenberg
author: Martin Loebl
published in: Journal of Algebraic Combinatorics
publication date: 1996-11-25T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 90B99
Mathematics Subject Classification ID: 20K99
zbMATH DE Number: 887237
zbMATH Keywords: polyhedral complexes
zbMATH Keywords: Robbins' theorem
zbMATH Keywords: strongly connected
zbMATH Keywords: orientations
zbMATH Keywords: connectivity
zbMATH Keywords: polyhedra
reviewed by: J. Neggers
MaRDI profile type: Publication
cites work: Q4693148
cites work: Q4871749
cites work: Q4120626
cites work: Total dual integrality and integer polyhedra
cites work: Q3827224
cites work: On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
cites work: A Theorem on Graphs, with an Application to a Problem of Traffic Control
cites work: Q3818127
cites work: Q3916595
full work available at URL: a:1022413100969
OpenAlex ID: W102559991
description: scientific article; zbMATH DE number 887237