Minimal n-fach zusammenhängende Digraphen |
| |
Authors: | W Mader |
| |
Affiliation: | Institut für Mathematik, Universität Hannover, Welfengarten 1, D-3000 Hannover 1, Germany |
| |
Abstract: | For a minimally n-connected digraph D, the subgraph spanned by the edges (x, y) with outdegree of x and indegree of y exceeding n is denoted by D0. It is proved that D0 corresponds to a forest. This implies that in a finite, minimally n-connected digraph D, the number of vertices of outdegree n is at least n and that the number of vertices of outdegree or indegree equal to n grows linearly in |D|. For almost every integer m, the maximum number of edges in a minimally n-connected digraph of order m is determined and the extremal digraphs are characterized. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|