A Study on the Existence of Null Labelling for 3-Hypergraphs

A 3-uniform hypergraph H consists of a set V of vertices, and E⊆(V3) triples. Let a null labelling be an assignment of ± 1 to the triples such that each vertex has signed degree equal to zero. Assumed as necessary condition the degree of every vertex of H to be even, the Null Labelling Problem consists in determining whether H has a null labelling. Although the problem is NP-complete, the subclasses where the problem turns out to be polynomially solvable are of interest. In this study we define the notion of 2-intersection graph related to a 3-uniform hypergraph, and we prove that the existence of a Hamiltonian cycle there, is sufficient to obtain a null labelling in the related hypergraph. The proof we propose provides an efficient way of computing the null labelling.