Theory and Applications of Graphs Theory and Applications of Graphs

Abstract

We define and study a special type of hypergraph. A σ -hypergraph H = H ( n, r, q | σ ), where σ 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 | K ∩ V i | , 1 ≤ i ≤ n , is σ . The non-empty intersections K ∩ V i are called the parts of K , and s ( σ ) 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 σ -hypergraphs contain a Hamiltonian Berge cycle and that, for n ≥ s + 1 and q ≥ r ( r − 1), a σ -hypergraph H always contains a sharp Hamiltonian cycle. We also extend this result to k -intersecting cycles.