Circular-arc hypergraphs: Rigidity via connectedness

详细信息    查看全文

• 作者：Johannes Kö ; bler ; Sebastian Kuhnert ; Oleg Verbitsky ; ¹ ; ^{verbitsk@informatik.hu-berlin.de}
• 关键词：Circular-arc hypergraphs ; Circular-ones property ; Intersection graphs ; Proper circular-arc graphs ; Unique representations ; Graph canonization
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P2
• 页码：220-228
• 全文大小：448 K
• 卷排序：217

文摘

A circular-arc hypergraph  HH is a hypergraph admitting an arc ordering  , that is, a circular ordering of the vertex set V(H)V(H) such that every hyperedge is an arc of consecutive vertices. We give a criterion for the uniqueness of an arc ordering in terms of connectedness properties of HH. This generalizes the relationship between rigidity and connectedness disclosed by Chen and Yesha (1991) in the case of interval hypergraphs. Moreover, we state sufficient conditions for the uniqueness of tight   arc orderings where, for any two hyperedges AA and BB such that A⊆B≠V(H)A⊆B≠V(H), the corresponding arcs must share a common endpoint. We notice that these conditions are obeyed for the closed neighborhood hypergraphs of proper circular-arc graphs, implying for them the known rigidity results that were originally obtained using the theory of local tournament graph orientations.