Hamiltonicity and $σ$-hypergraphs

Christina Zarb

Published 2014-07-17Version 1

We define and study a special type of hypergraph. A $\sigma$-hypergraph $H= H(n,r,q$ $\mid$ $\sigma$), where $\sigma$ is a partition of $r$, is an $r$-uniform hypergraph having $nq$ vertices partitioned into $ n$ classes of $q$ vertices each. If the classes are denoted by $V_1$, $V_2$,...,$V_n$, then a subset $K$ of $V(H)$ of size $r$ is an edge if the partition of $r$ formed by the non-zero cardinalities $ \mid$ $K$ $\cap$ $V_i \mid$, $ 1 \leq i \leq n$, is $\sigma$. The non-empty intersections $K$ $\cap$ $V_i$ are called the parts of $K$, and $s(\sigma)$ denotes the number of parts. We consider various types of cycles in hypergraphs such as Berge cycles and sharp cycles in which only consecutive edges have a nonempty intersection. We show that most $\sigma$-hypergraphs contain a Hamiltonian Berge cycle and that, for $n \geq s+1$ and $q \geq r(r-1)$, a $\sigma$-hypergraph $H$ always contains a sharp Hamiltonian cycle. We also extend this result to $k$-intersecting cycles.