Given a 3-uniform hypergraph H having a set V of vertices, and a set of hyperedges T subset of P(V), whose elements have cardinality three each, a null labelling is an assignment of +/- 1 to the hyperedges such that each vertex belongs to the same number of hyperedges labelled +1 and -1. A sufficient condition for the existence of a null labelling of H (proved in Di Marco et al. Lect Notes Comput Sci 12757:282-294, 2021) is a Hamiltonian cycle in its 2-intersection graph. The notion of 2-intersection graph generalizes that of intersection graph of an (hyper)graph and extends its effectiveness. The present study first shows that this sufficient condition for the existence of a null labelling in H can not be weakened by requiring only the connectedness of the 2-intersection graph. Then some interesting properties related to their clique configurations are proved. Finally, the main result is proved, the NP-completeness of this characterization and, as a consequence, of the construction of the related 3-hypergraphs.

Structure and Complexity of 2-Intersection Graphs of 3-Hypergraphs / Andrea Frosini, Niccolò Di Marco, William Lawrence Kocay, Elisa Pergola, Lama Tarsissi. - In: ALGORITHMICA. - ISSN 1432-0541. - ELETTRONICO. - 85:(2022), pp. 745-761. [10.1007/s00453-022-00990-4]

Structure and Complexity of 2-Intersection Graphs of 3-Hypergraphs

Andrea Frosini;Niccolò Di Marco;Elisa Pergola;Lama Tarsissi
2022

Abstract

Given a 3-uniform hypergraph H having a set V of vertices, and a set of hyperedges T subset of P(V), whose elements have cardinality three each, a null labelling is an assignment of +/- 1 to the hyperedges such that each vertex belongs to the same number of hyperedges labelled +1 and -1. A sufficient condition for the existence of a null labelling of H (proved in Di Marco et al. Lect Notes Comput Sci 12757:282-294, 2021) is a Hamiltonian cycle in its 2-intersection graph. The notion of 2-intersection graph generalizes that of intersection graph of an (hyper)graph and extends its effectiveness. The present study first shows that this sufficient condition for the existence of a null labelling in H can not be weakened by requiring only the connectedness of the 2-intersection graph. Then some interesting properties related to their clique configurations are proved. Finally, the main result is proved, the NP-completeness of this characterization and, as a consequence, of the construction of the related 3-hypergraphs.
2022
85
745
761
Andrea Frosini, Niccolò Di Marco, William Lawrence Kocay, Elisa Pergola, Lama Tarsissi
File in questo prodotto:
File Dimensione Formato  
structure and complexity.pdf

accesso aperto

Tipologia: Pdf editoriale (Version of record)
Licenza: Open Access
Dimensione 1.08 MB
Formato Adobe PDF
1.08 MB 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/1286783
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact