کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4654086 1632808 2011 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Optimal guard sets and the Helly property
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Optimal guard sets and the Helly property
چکیده انگلیسی

In a set system FF, a guard set of an F∈FF∈F is a subset B⊆FB⊆F such that BB intersects all those F′∈FF′∈F which meet FF but are not contained in FF. Given a graph GG, we consider set systems FF whose intersection graph is GG, and determine one such FF in which the guard sets of all F∈FF∈F are as small as possible. We prove that the minimum–both in global and local sense–is attained by the dual of the clique hypergraph of GG, a structure which also played an important role in the proof of the Perfect Graph Theorem. We also put some remarks concerning algorithmic complexity.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 32, Issue 1, January 2011, Pages 28–32
نویسندگان
, ,