turkmath.org

The domination number of a graph is the order of the fewest number of vertices having the property that each vertex not in the set is adjacent to some vertex in the set. In general, computing the domination number of a graph is difficult. But we consider a fast algorithm that comes close to finding the minimum value. Further, we look at a fractional version of the problem. That is, we attach to each vertex a nonnegative number in such a manner that when we sum across all closed neighborhoods, we get a value of at least one. Further, we take one such labeling where the sum of all labels is minimized. This minimum sum forms a lower bound on the domination number. We use the random graph, as developed in previous lectures, to show how far apart these parameters can be.