Optimal guard sets and the Helly property (Q607361): Difference between revisions

Let \(\mathcal{F}\) be a family of sets, and \(F\in \mathcal{F}.\) Then \( B\subset F\) is called a guard set of \(F\) if for all \(F^{\prime }\in \mathcal{ F}\) so that \(F^{\prime }\cap F\neq \emptyset ,\) and \(F^{\prime }\varsubsetneq F\) it is \(B\cap F^{\prime }\neq \emptyset .\) The following problem is studied. Given a graph \(G.\) Find a family of sets \(\mathcal{F}\) such that \(G\) is the intersection graph of \(\mathcal{F}\) and the guard sets of all \(F\in \mathcal{F}\) are as small as possible. It is shown that the minimum is attained by the dual of the clique hypergraph of \(G.\)