Packing many dominating sets in a graph
Time: 14:00 -- Location: bat 650, 445
summary: 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. 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 say that a class of graph is DOM-bounded if there exists an increasing lower bound in terms of the minimum degree for the domatic number of all graphs within that class, and we wonder under what conditions a class of graphs is DOM-bounded. We present a probabilistic technique, relying mainly on the celebrated Lovász Local Lemma, to establish a pseudo-linear lower bound in terms of the minimum degree for the domatic number of some classes of graphs, such as regular graphs, unit disc graphs, and star-free graphs. We also discuss cographs and line graphs and propose a linear lower bound in terms of the minimum degree for their domatic number.