Premium
On critically connected digraphs
Author(s) -
Mader W.
Publication year - 1989
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.3190130412
Subject(s) - digraph , combinatorics , vertex (graph theory) , strongly connected component , mathematics , vertex connectivity , discrete mathematics , graph
A digraph is called critically connected if it is connected, but the deletion of any vertex destroys the connectivity. We prove that every critically connected finite digraph has at least two vertices of outdegree one. As an application, we show that for n ≧ 2, there is no n ‐connected, non‐complete, finite digraph such that the deletion of any n vertices results in a disconnected digraph.