×

zbMATH — the first resource for mathematics

Minimal n-fach zusammenhängende Digraphen. (Minimally n-connected digraphs). (German) Zbl 0578.05045
The author has proved [Arch. Math. 23, 219-224 (1972; Zbl 0212.294), 553-560 (1972; Zbl 0228.05119)] that in an undirected minimally n- connected graph the subgraph spanned by the vertices of degree greater than n corresponds to a forest. In this article he examines the directed case and proves that in each minimally n-connected digraph, the subgraph spanned by the edges (x,y) with outdegree of X and indegree of Y exceeding n contains no alternating cycle. Therefore this subgraph corresponds to a forest. From this he deduces some theorems on the maximum number of edges in minimally n-connected graphs and characterizes extremal digraphs.
Reviewer: M.Hager

MSC:
05C40 Connectivity
05C20 Directed graphs (digraphs), tournaments
05C35 Extremal problems in graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bermond, J.C; Thomassen, C, Cycles in digraphs—a survey, J. graph theory, 5, 1-43, (1981) · Zbl 0458.05035
[2] Cai, M.-C, Minimally k-connected graphs of low order and maximal size, Discrete math., 41, 229-234, (1982) · Zbl 0522.05040
[3] Dalmazzo, M, Nombre d’arcs dans LES graphes k-arc-fortement connexes minimaux, C. R. acad. sci. Paris Sér. A, 285, 341-344, (1977) · Zbl 0367.05037
[4] Halin, R, A theorem on n-connected graphs, J. combin. theory, 7, 150-154, (1969) · Zbl 0172.25803
[5] Halin, R, Unendliche minimale n-fach zusammenhängende graphen, Abh. math. sem. univ. Hamburg, 36, 75-88, (1971) · Zbl 0204.57004
[6] Hamidoune, Y.O, Sur LES sommets de demi-degré h d’un graphe fortement h-connexe minimal, C. R. acad. sci. Paris Sér. A, 286, 863-865, (1978) · Zbl 0376.05039
[7] Hamidoune, Y.O, Quelques problèmes de connexité dans LES graphes orientés, J. combin. theory ser. B, 30, 1-10, (1981) · Zbl 0475.05039
[8] Kameda, T, Note on Halin’s theorem on minimally connected graphs, J. combin. theory ser. B, 17, 1-4, (1974) · Zbl 0279.05110
[9] Mader, W, Minimale n-fach zusammenhängende graphen mit maximaler kantenzahl, J. reine angew. math., 249, 201-207, (1971) · Zbl 0214.51502
[10] Mader, W, Ecken vom Grad n in minimalen n-fach zusammenhängenden graphen, Arch. math., 23, 219-224, (1972) · Zbl 0212.29402
[11] Mader, W, Über minimal n-fach zusammenhängende, unendliche graphen und ein extremalproblem, Arch. math., 23, 553-560, (1972) · Zbl 0228.05119
[12] Mader, W, Ecken von innen- und außengrad n in minimal n-fach kantenzusammenhängenden digraphen, Arch. math., 25, 107-112, (1974) · Zbl 0259.05115
[13] Mader, W, Zur struktur minimal n-fach zusammenhängender graphen, Abh. math. sem. univ. Hamburg, 49, 49-69, (1979) · Zbl 0404.05041
[14] Mader, W, Konstruktion aller n-fach kantenzusammenhängenden digraphen, European J. combin., 3, 63-67, (1982) · Zbl 0488.05037
[15] Wagner, K, Graphentheorie, (1970), Bibliographisches Inst Mannheim · Zbl 0195.54103
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.