Séminaire Algorithmique : « Packing many dominating sets in a graph », François Pirot (LISN, Univ. Paris-Saclay)

Given a graph G, a dominating set of G is a subset of vertices S such that every vertex not in S is adjacent to at least one vertex in S; that is, NG[S] = V(G). While classical studies focus on finding the smallest dominating set of G, our focus shifts to finding the maximum number of disjoint dominating sets in G, i.e. its domatic number DOM(G). One can observe that for every graph G of minimum degree d ≥ 1, 2 ≤ DOM(G) ≤ d + 1, and both these bounds are tight regardless of the value of d. We are interested, on the contrary, in classes of graphs where the above lower bound is not tight, and to that end introduce the notion of DOM-boundedness. We say that a class of graphs C is DOM-bounded if there exists a function fC → ∞ such that DOM(G) ≥ fC (δ(G)) for every graph G ∈ C, where δ(G) denotes the minimum degree of G. In that case, we say that fC is a DOM-binding function of C.

We present a probabilistic technique, relying mainly on the celebrated Lovasz Local Lemma, to exhibit pseudo-linear DOM-binding functions for several classes of graphs, such as regular graphs, unit disk graphs, and star-free graphs. We also discuss cographs and line graphs, which turn out to have a linear DOM-binding function.

Joint work with Quentin Chuet, Selma Djelloul, Hoang La, and Hossein Zaredehabadi.