Strong connectivity of polyhedral complexes (Q1915156): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
Set OpenAlex properties.
 
(2 intermediate revisions by 2 users not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4693148 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4871749 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4120626 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Total dual integrality and integer polyhedra / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3827224 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Theorem on Graphs, with an Application to a Problem of Traffic Control / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3818127 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3916595 / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1023/a:1022413100969 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W102559991 / rank
 
Normal rank

Latest revision as of 10:41, 30 July 2024

scientific article
Language Label Description Also known as
English
Strong connectivity of polyhedral complexes
scientific article

    Statements

    Strong connectivity of polyhedral complexes (English)
    0 references
    0 references
    0 references
    25 November 1996
    0 references
    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.
    0 references
    polyhedral complexes
    0 references
    Robbins' theorem
    0 references
    strongly connected
    0 references
    orientations
    0 references
    connectivity
    0 references
    polyhedra
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references