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 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| الملخص: | 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. |
|---|