×

zbMATH — the first resource for mathematics

Detachments of amalgamated 3-uniform hypergraphs: factorization consequences. (English) Zbl 1258.05087
Summary: A detachment of a hypergraph \(\mathcal F\) is a hypergraph obtained from \(\mathcal F\) by splitting some or all of its vertices into more than one vertex. Amalgamating a hypergraph \(\mathcal G\) can be thought of as taking \(\mathcal G\), partitioning its vertices, then for each element of the partition squashing the vertices to form a single vertex in the amalgamated hypergraph \(\mathcal F\).
In this paper, we use Nash-Williams lemma on laminar families to prove a detachment theorem for amalgamated 3-uniform hypergraphs, which yields a substantial generalization of previous amalgamation theorems by Hilton, Rodger, and Nash-Williams.
To demonstrate the power of our detachment theorem, we show that the complete 3-uniform \(n\)-partite multihypergraph \(\lambda K^{3}_{m_{1},\dots ,m_n}\) can be expressed as the union \(\mathcal G_{1} \cup \dots \cup \mathcal G_{k}\) of \(k\) edge-disjoint factors, where for \(i=1,\dots,k\), \(\mathcal G_{i}\) is \(r_i\)-regular, if and only if:
(i)
\(m_{i}=m_j\) for all \(1\leq i,j \leq k\)
(ii)
\(3 \mid r_{i}mn\) for each \(i\), \(1 \leq i \leq k\), and
(iii)
\(\sum^{k}_{i=1} r_{i} = \lambda \binom{n-1}{2} m^2 \).

MSC:
05C65 Hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andersen, Generalized Latin rectangles I: Construction and decomposition, Discrete Math 31 (2) pp 125– (1980) · Zbl 0443.05019
[2] Andersen, Generalized Latin rectangles II: Embedding, Discrete Math 31 (3) pp 235– (1980) · Zbl 0476.05018
[3] Andersen, Decompositions of complete graphs: Embedding partial edge-colourings and the method of amalgamations, Surveys in Combinatorics, Lond Math Soc Lect Note Ser 307 pp 7– (2003) · Zbl 1028.05083
[4] M. A. Bahmanian Amalgamations and Detachments of Graphs and Hypergraphs 2012
[5] M. A. Bahmanian C. A. Rodger Extending partial edge-colorings of complete 3-uniform hypergraphs to r -factorizations
[6] Zs. Baranyai On the factorization of the complete uniform hypergraph in Infinite and Finite Sets (Colloq., Keszthely, 1973; dedicated to P. Erdos on his 60th birthday) 10 North-Holland Amsterdam 1975 91 108
[7] Baranyai, The edge-coloring of complete hypergraphs I, J Combin Theory B 26 (3) pp 276– (1979) · Zbl 0413.05040 · doi:10.1016/0095-8956(79)90002-9
[8] Berge, Hypergraphs (1989)
[9] Berg, Highly edge-connected detachments of graphs and digraphs, J Graph Theory 43 pp 67– (2003) · Zbl 1014.05043
[10] Brouwer, Packing and Covering in Combinatorics pp 39– (1979)
[11] H. Buchanan II Graph factors and Hamiltonian decompositions 1997
[12] Hilton, Hamilton decompositions of complete graphs, J Combin Theory B 36 pp 125– (1984) · Zbl 0542.05044 · doi:10.1016/0095-8956(84)90020-0
[13] Hilton, Amalgamations of connected k-factorizations, J Combin Theory B 88 pp 267– (2003) · Zbl 1033.05084 · doi:10.1016/S0095-8956(03)00030-3
[14] Hilton, Hamilton decompositions of complete regular s-partite graphs, Discrete Math 58 pp 63– (1986) · Zbl 0593.05047
[15] Jackson, Non-separable detachments of graphs, Dedicated to Crispin St. J. A. Nash-Williams, J Combin Theory Ser B 87 pp 17– (2003)
[16] Johnson, Amalgamations of factorizations of complete graphs, J Combin Theory B 97 pp 597– (2007) · Zbl 1153.05055 · doi:10.1016/j.jctb.2006.09.004
[17] Jungnickel, Graphs, networks and algorithms (2008)
[18] Kirkman, On a problem in combinations, Camb Dublin Math J 2 pp 191– (1847)
[19] Laskar, On the decompositions of r-partite graphs into edge-disjoint hamilton circuits, Discrete Math 14 pp 146– (1976) · Zbl 0322.05128
[20] Leach, Non-disconnecting disentanglements of amalgamated 2-factorizations of complete multipartite graphs, J Combin Des 9 pp 460– (2001) · Zbl 0994.05125
[21] Leach, Hamilton decompositions of complete multipartite graphs with any 2-factor leave, J Graph Theory 44 pp 208– (2003) · Zbl 1031.05108
[22] Leach, Hamilton decompositions of complete graphs with a 3-factor leave, Discrete Math 279 pp 337– (2004) · Zbl 1044.05058
[23] Lucas, Récréations Mathématiques 2 (1892)
[24] Nash-Williams, Connected detachments of graphs and generalized Euler trails, J London Math Soc 31 pp 17– (1985) · Zbl 0574.05042
[25] Nash-Williams, Surveys in Combinatorics 1985, London Mathematical Society 103 pp 137– (1985) · doi:10.1017/CBO9781107325678.008
[26] Nash-Williams, Amalgamations of almost regular edge-colourings of simple graphs, J Combin Theory B 43 pp 322– (1987) · Zbl 0654.05031 · doi:10.1016/0095-8956(87)90008-6
[27] R. Peltesohn Das Turnierproblem für Spiele zu je dreien 1936 · Zbl 0013.33805
[28] Ray-Chaudhuri, A Survey of Combinatorial Theory pp 361– (1973) · doi:10.1016/B978-0-7204-2262-7.50035-1
[29] Rodger, Embedding hyperedge-colorings into 2-edge-connected k-factorizations of Kkn+1, J Graph Theory 10 pp 169– (1995) · Zbl 0815.05050
[30] de Werra, Balanced schedules, INFOR-Canad J Oper Res Inform Process 9 pp 230– (1971)
[31] de Werra, Equitable colorations of graphs, Rev Fran Inf Rech Oper 5 pp 3– (1971)
[32] de Werra, A few remarks on chromatic scheduling, Combinatorial programming methods and applications pp 337– (1975)
[33] de Werra, On a particular conference scheduling problem, INFOR-Canad J Oper Res Inform Process 13 (3) pp 308– (1975) · Zbl 0352.90032
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.