کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949795 | 1364257 | 2017 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Circular-arc hypergraphs: Rigidity via connectedness
ترجمه فارسی عنوان
هیپرگرافهای دیفرانسیل-قوس: سختی از طریق همبستگی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 217, Part 2, 30 January 2017, Pages 220-228
Journal: Discrete Applied Mathematics - Volume 217, Part 2, 30 January 2017, Pages 220-228
نویسندگان
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky,