Article ID Journal Published Year Pages File Type
4654086 European Journal of Combinatorics 2011 5 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,