Circular-arc hypergraphs: Rigidity via connectedness
Circular-arc hypergraphs: Rigidity via connectedness
复制标题
圆弧超图：通过连通性实现刚性
DOI：
10.1016/j.dam.2016.08.008
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
O. Verbitsky
中科院分区：
文献类型：
--
作者：
J. K¨bler;S. Kuhnert;O. Verbitsky
圆弧超图H是允许弧序的超图，即顶点集V(H)的圆序，使得每条超边都是由连续顶点组成的弧。利用H的连通性给出了弧序唯一性的一个判据，推广了Chen和Yesha(1991)在区间超图中揭示的刚性与连通性之间的关系.此外，我们还给出了紧圆弧序唯一性的充分条件，其中对于任何两条超边A和B，使得A⊆B≠V(H)，对应的圆弧必须共享一个公共端点。我们注意到，对于真圆弧图的闭邻域超图，这些条件是满足的，这意味着对它们来说，最初利用局部竞赛图定向理论得到的已知刚性结果。
A circular-arc hypergraph H is a hypergraph admitting an arc ordering, that is, a circular ordering of the vertex set 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 H. 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 A and B such that 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.
登录
查看更多内容
影响因子：
0.8
作者：
J. Bang;Jing Huang;Anders Yeo
通讯作者：
Anders Yeo
解决对数空间中适当圆弧图的规范表示和星系统问题
DOI：
10.1016/j.jda.2016.03.001
发表时间：
2016
期刊：
影响因子：
--
作者：
J. Köbler;S. Kuhnert;O. Verbitsky
通讯作者：
O. Verbitsky
DOI：
10.1016/0012-365x(84)90006-2
发表时间：
1984
期刊：
Discret. Math.
影响因子：
--
作者：
A. Quilliot
通讯作者：
A. Quilliot
影响因子：
1.1
作者：
Francisco J. Soulignac
通讯作者：
Francisco J. Soulignac
与circular-ones属性相关的图类同构
DOI：
10.46298/dmtcs.625
发表时间：
2012
期刊：
Discret. Math. Theor. Comput. Sci.
影响因子：
--
作者：
Andrew R. Curtis;Min Chih Lin;R. McConnell;Yahav Nussbaum;Francisco J. Soulignac;J. Spinrad;J. Szwarcfiter
通讯作者：
J. Szwarcfiter