On decomposing a hypergraph into k connected sub-hypergraphs

被引：60

作者：

Frank, A

Király, T

Kriesell, M

机构：

[1] Eotvos Lorand Univ, Dept Operat Res, H-1117 Budapest, Hungary

[2] Traffic Lab Ericsson Hungary, H-1037 Budapest, Hungary

[3] Leibniz Univ Hannover, Inst Math, D-30167 Hannover, Germany

[4] Univ Bonn, Inst Discrete Math, D-5300 Bonn, Germany

来源：

DISCRETE APPLIED MATHEMATICS | 2003年 / 131卷 / 02期

关键词：

D O I：

10.1016/S0166-218X(02)00463-8

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

By applying the matroid partition theorem of J. Edmonds (J. Res. Nat. Bur. Standards Sect. B 69 (1965) 67) to a hypergraphic generalization of graphic matroids, due to Lorea (Cahiers Centre Etudes Rech. Oper. 17 (1975) 289), we obtain a generalization of Tutte's disjoint trees theorem for hypergraphs. As a corollary, we prove for positive integers k and q that every (kq)-edge-connected hypergraph of rank q can be decomposed into k connected sub-hypergraphs, a well-known result for q = 2. Another by-product is a connectivity-type sufficient condition for the existence of k edge-disjoint Steiner trees in a bipartite graph. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：373 / 383

页数：11

共 7 条

[1]

[Anonymous], ANN DISCRETE MATH

[2]

[Anonymous], 1961, Journal of the London Mathematical Society, DOI DOI 10.1112/JLMS/S1-36.1.221

[3] MINIMUM PARTITION OF A MATROID INTO INDEPENDENT SUBSETS [J].

EDMONDS, J .

JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL, 1965, B 69 (1-2) :67-+

[4]

Edmonds J., 1970, Combinatorial Structures and Their Applications, P69, DOI DOI 10.1007/3-540-36478

[5]

Lorea M., 1975, Cahiers Centre Etudes Rech. Oper., V17, P289

[6] GENERALIZATION OF KONIGS THEOREM [J].

LOVASZ, L .

ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1970, 21 (3-4) :443-&

[7]

NashWilliams C. St. J. A., 1964, Journal of the London Mathematical Society, V1, P12

← 1 →