Dear all,
There will be a noon seminar this Thursday, 17 October, given by Yelena Yuditsky. Please find the talk details below.
Best regards, Misha Tyomkyn.
--------------------------------------------------------------------------
Domination and packing in graphs Yelena Yuditsky Université libre de Bruxelles October 17, 2024, 12:20 in S6
Abstract 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.
--------------------------------------------------------------------------