Degree and local connectivity in digraphs (Q1065027): Difference between revisions

In this paper the author studies the relation between the degrees of the vertices of a digraph and the maximum number of paths between two vertices in it. The results proved in a previous article [Grad und lokaler Zusammenhang in endlichen Graphen, Math. Ann. 205, 9-11 (1973; Zbl 0245.05119)] for simple graphs cannot be extended to digraphs. For every m the author constructs digraphs in which every vertex has an outdegree at least 12m but the maximum number of openly disjoint paths between two vertices is only 11m. More positive results are given in the case of edge-disjoint paths. For example, the maximum number of edge- disjoint paths between two vertices is at least the minimum outdegree minus one. The author also studies the case of directed multigraphs and gives conjectures.