Structure and Complexity of 2-Intersection Graphs of 3-Hypergraphs
Given a 3-uniform hypergraph H having a set V of vertices, and a set of hyperedges T ⊂ 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...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | , , , |
| منشور في: |
2023
|
| الموضوعات: | |
| الوصول للمادة أونلاين: | https://depot.sorbonne.ae/handle/20.500.12458/1367 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1857415064318902272 |
|---|---|
| author | Tarsissi, Lama |
| author2 | Kocay, William Lawrence Di Marco, Niccoló Frosini, Andrea Pergola, Elisa |
| author2_role | author author author author |
| author_facet | Tarsissi, Lama Kocay, William Lawrence Di Marco, Niccoló Frosini, Andrea Pergola, Elisa |
| author_role | author |
| dc.creator.none.fl_str_mv | Tarsissi, Lama Kocay, William Lawrence Di Marco, Niccoló Frosini, Andrea Pergola, Elisa |
| dc.date.none.fl_str_mv | 2023-01-04T05:38:12Z 2023-01-04T05:38:12Z 2023 |
| dc.format.none.fl_str_mv | application/pdf |
| dc.identifier.none.fl_str_mv | 10.1007/s00453-022-00990-4 0178-4617 1432-0541 https://depot.sorbonne.ae/handle/20.500.12458/1367 10.1007/s00453-022-00990-4 |
| dc.language.none.fl_str_mv | en |
| dc.relation.none.fl_str_mv | Algorithmica 1432-0541 |
| dc.subject.none.fl_str_mv | 3-hypergraph Null labelling Reconstruction problem NP-completeness Mathematics Subject Classification 05C65 05C22 05C85 05C99 |
| dc.title.none.fl_str_mv | Structure and Complexity of 2-Intersection Graphs of 3-Hypergraphs |
| dc.type.none.fl_str_mv | Controlled Vocabulary for Resource Type Genres::text::periodical::journal::contribution to journal::journal article |
| description | Given a 3-uniform hypergraph H having a set V of vertices, and a set of hyperedges T ⊂ 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 3hypergraphs. |
| id | sorbonner_7e58f88757662e566298424ef6b6b44b |
| identifier_str_mv | 10.1007/s00453-022-00990-4 0178-4617 1432-0541 |
| language_invalid_str_mv | en |
| network_acronym_str | sorbonner |
| network_name_str | Sorbonne University Abu Dhabi repository |
| oai_identifier_str | oai:depot.sorbonne.ae:20.500.12458/1367 |
| publishDate | 2023 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Structure and Complexity of 2-Intersection Graphs of 3-HypergraphsTarsissi, LamaKocay, William LawrenceDi Marco, NiccolóFrosini, AndreaPergola, Elisa3-hypergraphNull labellingReconstruction problemNP-completeness Mathematics Subject Classification 05C6505C2205C8505C99Given a 3-uniform hypergraph H having a set V of vertices, and a set of hyperedges T ⊂ 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 3hypergraphs.2023-01-04T05:38:12Z2023-01-04T05:38:12Z2023Controlled Vocabulary for Resource Type Genres::text::periodical::journal::contribution to journal::journal articleapplication/pdf10.1007/s00453-022-00990-40178-46171432-0541https://depot.sorbonne.ae/handle/20.500.12458/136710.1007/s00453-022-00990-4enAlgorithmica1432-0541oai:depot.sorbonne.ae:20.500.12458/13672023-04-26T06:31:17Z |
| spellingShingle | Structure and Complexity of 2-Intersection Graphs of 3-Hypergraphs Tarsissi, Lama 3-hypergraph Null labelling Reconstruction problem NP-completeness Mathematics Subject Classification 05C65 05C22 05C85 05C99 |
| title | Structure and Complexity of 2-Intersection Graphs of 3-Hypergraphs |
| title_full | Structure and Complexity of 2-Intersection Graphs of 3-Hypergraphs |
| title_fullStr | Structure and Complexity of 2-Intersection Graphs of 3-Hypergraphs |
| title_full_unstemmed | Structure and Complexity of 2-Intersection Graphs of 3-Hypergraphs |
| title_short | Structure and Complexity of 2-Intersection Graphs of 3-Hypergraphs |
| title_sort | Structure and Complexity of 2-Intersection Graphs of 3-Hypergraphs |
| topic | 3-hypergraph Null labelling Reconstruction problem NP-completeness Mathematics Subject Classification 05C65 05C22 05C85 05C99 |
| url | https://depot.sorbonne.ae/handle/20.500.12458/1367 |