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.

A Study on the Existence of Null Labelling for 3-Hypergraphs / Niccolò Di Marco; Andrea Frosini; William Lawrence Kocay. - STAMPA. - 12757:(2021), pp. 282-294. (Intervento presentato al convegno 32nd International Workshop on Combinatorial Algorithms, IWOCA 2021 nel 2021) [10.1007/978-3-030-79987-8_20].

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

Niccolò Di Marco;Andrea Frosini;
2021

Abstract

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.
2021
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
32nd International Workshop on Combinatorial Algorithms, IWOCA 2021
2021
Niccolò Di Marco; Andrea Frosini; William Lawrence Kocay
File in questo prodotto:
File Dimensione Formato  
A_study_on_the_existence_of_null_labelling_for_3_hypergraphs.pdf

accesso aperto

Tipologia: Altro
Licenza: Tutti i diritti riservati
Dimensione 372.46 kB
Formato Adobe PDF
372.46 kB Adobe PDF

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1242518
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact