✦ LIBER ✦

On decomposing a hypergraph into k connected sub-hypergraphs

✍ Scribed by András Frank; Tamás Király; Matthias Kriesell

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 159 KB
Volume: 131
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(02)00463-8

No coin nor oath required. For personal study only.

✦ Synopsis

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 su cient condition for the existence of k edge-disjoint Steiner trees in a bipartite graph.

📜 SIMILAR VOLUMES

On the decomposition of a minimally stro

On the decomposition of a minimally strongly h-connected digraph into h+1 acircuitic sub-graphs

✍ Yahya Ould Hamidoune 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 119 KB

We prove that every minimally strongly h-connected digraph can be decomposed into h + 1 acircuitic subgraphs. This result generalizes the following theorem of Mader. Every minimally h-connected graph is h + 1 colourable,