×

zbMATH — the first resource for mathematics

Connected Baranyai’s theorem. (English) Zbl 1324.05053
Let \(\lambda K_{n}^{h}\) be the complete \(h\)-uniform hypergraph with \(n\) vertices and every edge of multiplicity \(\lambda\) and \(r_1+r_2+\dots +r_k=\lambda {{n-1}\choose{h-1}}\). Then, an \((r_1,r_2,\dots,r_k)\)-factorization of \(\lambda K_{n}^{h}\) is a partition of the edge set of \(\lambda K_{n}^{h}\) into factors \(F_1,F_2,\dots,F_k\), where \(F_i\) is \(r_i\)-regular. When \(r_1=r_2=\dots=r_k=r\), then the factorization is called an \(r\)-factorization.
The well known Baranyai’s theorem states that \(K_{n}^{h}\) can be decomposed into edge-disjoint \(r\)-regular factors if and only if \(h\) divides \(rn\) and \(r\) divides \({n-1}\choose{h-1}\).
The author generalizes Baranyai’s result by proving that \(\lambda K_{n}^{h}\) has an \((r_1,r_2,\dots ,r_k)\)-factorization if and only if \(h\) divides \(r_i n\) for all \(r_i\), \(1\leq i\leq k,\) and \(\sum_{i=1}^{k}r_i=\lambda{{n-1}\choose{h-1}}\). Moreover, the result is strengthening Baranyai’s theorem because it further asserts that whenever \(r_i\geq 2\), the \(r_i\)-regular factor \(F_i\) can be guaranteed to be connected.

MSC:
05C15 Coloring of graphs and hypergraphs
05C40 Connectivity
05C51 Graph designs and isomorphic decomposition
05C65 Hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05B40 Combinatorial aspects of packing and covering
05B05 Combinatorial aspects of block designs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bahmanian, M A; Rodger, C A, Multiply balanced edge colorings of multigraphs, J. Graph Theory, 70, 297-317, (2012) · Zbl 1244.05085
[2] Bahmanian, M A, Detachments of amalgamated 3-uniform hypergrpahs I: factorization consequences, J. Combin. Designs, 20, 527-549, (2012) · Zbl 1258.05087
[3] Bahmanian, M A, Detachments of hypergraphs I: the berge-Johnson problem, Combin. Probab. Comput., 21, 483-495, (2012) · Zbl 1247.05161
[4] Bahmanian, M A; Rodger, C A, Embedding edge-colorings into Hamiltonian decompositions, Graphs and Combinatorics, 29, 747-755, (2013) · Zbl 1268.05050
[5] Bahmanian, M A; Rodger, C A, Extending partial edge-colorings of complete 3-uniform hypergraphs to r-factorizations, J. Graph Theory, 73, 216-224, (2013) · Zbl 1264.05088
[6] Baranyai, Zs, On the factorization of the complete uniform hypergraph, Colloq. Math. Soc. Janos Bolyai, 10, 91-108, (1975) · Zbl 0306.05137
[7] Hilton, A J W, Hamiltonian decompositions of complete graphs, J. Combin. Theory B, 36, 125-134, (1984) · Zbl 0542.05044
[8] Bahmanian, M A; Rodger, C A, Multiply balanced edge colorings of multigraphs, J. Graph Theory, 70, 297-317, (2012) · Zbl 1244.05085
[9] Bahmanian, M A, Detachments of amalgamated 3-uniform hypergrpahs I: factorization consequences, J. Combin. Designs, 20, 527-549, (2012) · Zbl 1258.05087
[10] Bahmanian, M A, Detachments of hypergraphs I: the berge-Johnson problem, Combin. Probab. Comput., 21, 483-495, (2012) · Zbl 1247.05161
[11] Bahmanian, M A; Rodger, C A, Embedding edge-colorings into Hamiltonian decompositions, Graphs and Combinatorics, 29, 747-755, (2013) · Zbl 1268.05050
[12] Bahmanian, M A; Rodger, C A, Extending partial edge-colorings of complete 3-uniform hypergraphs to r-factorizations, J. Graph Theory, 73, 216-224, (2013) · Zbl 1264.05088
[13] Baranyai, Zs, On the factorization of the complete uniform hypergraph, Colloq. Math. Soc. Janos Bolyai, 10, 91-108, (1975) · Zbl 0306.05137
[14] Hilton, A J W, Hamiltonian decompositions of complete graphs, J. Combin. Theory B, 36, 125-134, (1984) · Zbl 0542.05044
[15] Hilton, A J W; Rodger, C A, Hamilton decompositions of complete regular \(s\)-partite graphs, Discrete Math., 58, 63-78, (1986) · Zbl 0593.05047
[16] Johnson, M, Amalgamations of factorizations of complete graphs, J. Combin. Theory B, 97, 597-611, (2007) · Zbl 1153.05055
[17] Katona, G O H, Rényi and the combinatorial search problems, Studia Sci. Math. Hungar., 26, 363-378, (1991) · Zbl 0788.68004
[18] E. Lucas: Récréations Mathématiques, Vol. 2, Gauthiers Villars, Paris, 1883. · Zbl 1244.05085
[19] Nash-Williams, C St J A, Amalgamations of almost regular edge-colourings of simple graphs, J. Combin. Theory B, 43, 322-342, (1987) · Zbl 0654.05031
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.