Premium
On Vertices of outdegree n in minimally n ‐connected digraphs
Author(s) -
Mader W.
Publication year - 2002
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.10018
Subject(s) - digraph , combinatorics , conjecture , mathematics , vertex (graph theory) , strongly connected component , vertex connectivity , graph , connectivity , discrete mathematics
Let | D | and |D| + n denote the number of vertices of D and the number of vertices of outdegree n in the digraph D , respectively. It is proved that every minimally n ‐connected, finite digraph D has |D| + n ≥ n + 1 and that for n ≥ 2, there is a c n > 0 such that $|D|^+_n > C_n \sqrt{|D|}$ for all minimally n ‐connected, finite digraphs D . Furthermore, case n = 2 of the following conjecture is settled which says that every minimally n ‐connected, finite digraph has a vertex of indegree and outdegree equal to n . © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 129–144, 2002