کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872079 | 681717 | 2016 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Nordhaus-Gaddum-type problems for lines in hypergraphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We study the number of lines in hypergraphs in a symmetric setting, where both the hypergraph and its complement are considered. In the general case and in some special cases, the lower bounds on the number of lines are much higher than their counterparts in single hypergraph setting or admit more elegant proofs. We show that the minimum value of product of the number of lines in both hypergraphs on n points is easily determined as (n2); and the minimum value of their sum is between Ω(n) and O(nlogn). We also study some restricted classes of hypergraphs; and determine the tight bounds on the minimum sum when the hypergraph is derived from a Euclidean space, a real projective plane, or a tree.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 198, 10 January 2016, Pages 297-302
Journal: Discrete Applied Mathematics - Volume 198, 10 January 2016, Pages 297-302
نویسندگان
Xiaomin Chen, Peihan Miao,