Domination in graphs

Abstract: A dominating set in a graph G is a set of vertices D such that each vertex is either in D or has a neighbor in D. A partition of V (G) such that each class is a dominating set in G is called a domatic partition of G. In this thesis, we first briefly survey a variety of known results in the field, presenting fundamentals as well as more recent concepts in domination. In particular, we turn our attention to ordinary domination, factor domination (where D dominates every given spanning subgraph of G), and distance domination (where a vertex not in D is within a given distance from D). Our main contributions are in the area of factor domination. We first prove several probabilistic bounds on the size of a factor domatic partition as well as the size of a smallest factor dominating set. Then, using well-known Beck’s method, we obtain a polynomial time randomized algorithm that constructs such a partition. We also give similar bounds and algorithms for other related problems.