کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871598 1440187 2018 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Extremal hypergraphs for matching number and domination number
ترجمه فارسی عنوان
هیپرگراف های افراطی برای تعدیل تعداد و سلطه
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A matching in a hypergraph H is a set of pairwise disjoint hyperedges. The matching number ν(H) of H is the size of a maximum matching in H. A subset D of vertices of H is a dominating set of H if for every v∈V∖D there exists u∈D such that u and v lie in an hyperedge of H. The cardinality of a minimum dominating set of H is the domination number of H, denoted by γ(H). It was proved that γ(H)≤(r−1)ν(H) for r-uniform hypergraphs and the 2-uniform hypergraphs (graphs) achieving equality γ(H)=ν(H) have been characterized. In this paper we generalize the inequality γ(H)≤(r−1)ν(H) to arbitrary hypergraph of rank r and we completely characterize the extremal hypergraphs H of rank 3 achieving equality γ(H)=(r−1)ν(H).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 236, 19 February 2018, Pages 415-421
نویسندگان
, , , ,