Robbins theorem
E1015500
Robbins theorem is a result in graph theory that characterizes when a connected graph can be oriented to become strongly connected, providing a key condition for the existence of strongly connected orientations.
Statements (44)
| Predicate | Object |
|---|---|
| instanceOf |
result in graph theory
ⓘ
theorem ⓘ |
| appliesTo | finite undirected graphs ⓘ |
| assumes |
graph is connected
ⓘ
graph is finite ⓘ graph is undirected ⓘ |
| category |
theorems about connectivity
ⓘ
theorems in graph theory ⓘ |
| characterizes | when a connected graph admits a strongly connected orientation ⓘ |
| conclusion | there exists an orientation of every edge such that the resulting digraph is strongly connected ⓘ |
| conditionType | necessary and sufficient condition ⓘ |
| equivalentFormulation | A connected undirected graph has a strongly connected orientation if and only if it is 2-edge-connected ⓘ |
| field | graph theory ⓘ |
| generalizationOf | characterizations of strongly connected orientations of graphs ⓘ |
| hasApplication |
communication networks
ⓘ
network design ⓘ reliability of network connectivity ⓘ transportation networks ⓘ |
| implies |
every 2-edge-connected graph has a strongly connected orientation
ⓘ
if a connected graph has a bridge then it has no strongly connected orientation ⓘ |
| importance | fundamental result in graph orientation theory ⓘ |
| involvesObject |
directed graph
ⓘ
strongly connected digraph ⓘ undirected graph ⓘ |
| involvesProperty |
absence of bridges
ⓘ
edge-connectivity at least 2 ⓘ |
| namedAfter | Herbert E. Robbins NERFINISHED ⓘ |
| originalAuthor | Herbert E. Robbins NERFINISHED ⓘ |
| proofTechnique | graph-theoretic arguments ⓘ |
| publicationTitle | A theorem on graphs with an application to a problem of traffic control ⓘ |
| publicationYear | 1939 ⓘ |
| publishedIn | American Mathematical Monthly NERFINISHED ⓘ |
| relatedTo |
Menger theorem
NERFINISHED
ⓘ
edge-connectivity ⓘ graph orientation ⓘ strong connectivity ⓘ |
| states | A connected undirected graph has a strongly connected orientation if and only if it has no bridges ⓘ |
| status | proven ⓘ |
| usedFor | deciding existence of strongly connected orientations ⓘ |
| usesConcept |
2-edge-connected graph
ⓘ
bridge ⓘ connected graph ⓘ cut edge ⓘ strongly connected orientation ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.