Premium
On minimal strong blocks
Author(s) -
Grötschel Martin
Publication year - 1979
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190030303
Subject(s) - mathematics , combinatorics , bounded function , decomposition , discrete mathematics , biology , ecology , mathematical analysis
It is shown that storng blocks, i.e., digraphs that are strongly connected and have no cutnodes have an ear‐decomposition. This result is used to prove that the number q of arcs of minimal strong blocks is bounded by p ≤ q ≤ 2p – 3 and that minimal strong blocks contain at least two nodes with indegree and outdegree equal to one.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom