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