Premium
Decomposition of complete uniform multi‐hypergraphs into Berge paths and cycles
Author(s) -
Javadi Ramin,
Khodadadpour Afsaneh,
Omidi Gholamreza
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22226
Subject(s) - mathematics , combinatorics , multigraph , disjoint sets , conjecture , integer (computer science) , matching (statistics) , decomposition , pairwise comparison , enhanced data rates for gsm evolution , discrete mathematics , computer science , graph , ecology , telecommunications , statistics , biology , programming language
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 λ K n − 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 λ K nare also sufficient. In this article, first, we obtain the necessary and sufficient conditions for packing edge‐disjoint cycles of arbitrary lengths in λ K n − I . Then, applying this result, we investigate the analogous problem of the decomposition of the complete uniform multihypergraph μ K n ( k )into Berge cycles and paths of arbitrary given lengths. In particular, we show that for every integer μ ≥ 1 , n ≥ 108 and 3 ≤ k < n , μ K n ( k )can be decomposed into Berge cycles and paths of arbitrary lengths, provided that the obvious necessary conditions hold, thereby generalizing a result by Kühn and Osthus on the decomposition of K n ( k )into Hamilton Berge cycles.