Domination and packing in graphs

The dominating number of a graph is the minimum size of a vertex set whose closed neighborhoods cover all the vertices of the graph. The packing number of a graph is the maximum size of a vertex set whose closed neighborhoods are disjoint. We show constant bounds on the ratio of the above two parameters for various graph classes. For example, we improve the bound for planar graphs. The result implies a constant integrality gap for the domination and packing problems.

This is a joint work with Marthe Bonamy, Monika Csikos and Anna Gujgiczer.