Decomposition of complete uniform multi-hypergraphs into Berge paths and cycles

作者：Javadi Ramin^*; Khodadadpour Afsaneh; Omidi Gholamreza

来源：Journal of Graph Theory, 2018, 88(3): 507-520.

DOI：10.1002/jgt.22226

• Berge cycle
• Berge path
• cycle decomposition
• cycle packing
• hypergraph
• path decomposition

In 2015, Bryant, Horsley, Maenhaut, and Smith, generalizing a well-known conjecture by Alspach, obtained the necessary and sufficient conditions for the decomposition of the complete multigraph Kn-I into cycles of arbitrary lengths, where I is empty, when (n-1) is even and I is a perfect matching, when (n-1) is odd. Moreover, Bryant in 2010, verifying a conjecture by Tarsi, proved that the obvious necessary conditions for packing pairwise edge-disjoint paths of arbitrary lengths in Kn are also sufficient. In this article, first, we obtain the necessary and sufficient conditions for packing edge-disjoint cycles of arbitrary lengths in Kn-I. Then, applying this result, we investigate the analogous problem of the decomposition of the complete uniform multihypergraph into Berge cycles and paths of arbitrary given lengths. In particular, we show that for every integer 1, n108 and 3k

• 出版日期2018-7