کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421410 | 684221 | 2007 | 9 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Characterization and recognition of generalized clique-Helly graphs Characterization and recognition of generalized clique-Helly graphs](/preview/png/421410.png)
Let p⩾1p⩾1 and q⩾0q⩾0 be integers. A family of sets FF is (p,q)(p,q)-intersecting when every subfamily F′⊆FF′⊆F formed by p or less members has total intersection of cardinality at least q . A family of sets FF is (p,q)(p,q)-Helly when every (p,q)(p,q)-intersecting subfamily F′⊆FF′⊆F has total intersection of cardinality at least q. A graph G is a (p,q)(p,q)-clique-Helly graph when its family of (maximal) cliques is (p,q)(p,q)-Helly. According to this terminology, the usual Helly property and the clique-Helly graphs correspond to the case p=2,q=1p=2,q=1. In this work we present a characterization for (p,q)(p,q)-clique-Helly graphs. For fixed p,qp,q, this characterization leads to a polynomial-time recognition algorithm. When p or q is not fixed, it is shown that the recognition of (p,q)(p,q)-clique-Helly graphs is NP-hard.
Journal: Discrete Applied Mathematics - Volume 155, Issue 18, 1 November 2007, Pages 2435–2443