Article ID Journal Published Year Pages File Type
4655336 Journal of Combinatorial Theory, Series A 2014 8 Pages PDF
Abstract

In 1973 Bermond, Germa, Heydemann and Sotteau conjectured that if n   divides (nk), then the complete k-uniform hypergraph on n   vertices has a decomposition into Hamilton Berge cycles. Here a Berge cycle consists of an alternating sequence v1,e1,v2,…,vn,env1,e1,v2,…,vn,en of distinct vertices vivi and distinct edges eiei so that each eiei contains vivi and vi+1vi+1. So the divisibility condition is clearly necessary. In this note, we prove that the conjecture holds whenever k≥4k≥4 and n≥30n≥30. Our argument is based on the Kruskal–Katona theorem. The case when k=3k=3 was already solved by Verrall, building on results of Bermond.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,