Perfect f-Matchings and f-Factors in Hypergraphs - A Combinatorial Approach
- We prove characterizations of the existence of perfect f-matchings in uniform mengerian and perfect hypergraphs. Moreover, we investigate the f-factor problem in balanced hypergraphs. For uniform balanced hypergraphs we prove two existence theorems with purely combinatorial arguments, whereas for non-uniform balanced hypergraphs we show that the f-factor problem is NP-hard.
|Author:||Isabel Beckenbach, Robert Scheidweiler|
|Tag:||Hall's Theorem; balanced hypergraph; f-factors in hypergraphs; mengerian hypergraph; perfect f-matchings in hypergraphs; perfect hypergraph|
|MSC-Classification:||05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C65 Hypergraphs|
|05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C70 Factorization, matching, partitioning, covering and packing|
|Date of first Publication:||2016/06/04|
|Series (Serial Number):||ZIB-Report (16-22)|