Relating the size of a connected graph to its total and restricted domination numbers Original Research Article

A dominating set for a graph G=(V,E) is a subset of vertices D⊆V such that for all v∈V−D there exists some u∈D adjacent to v. The domination number of G is the size of its smallest dominating set. A dominating set D is a total dominating set if every vertex in D has a neighbor in D. We give a tight upper bound on the number of edges that a connected graph with a given total domination number can have, and characterize the extremal graphs attaining the bound. We do the same for the k-restricted domination number, which is the smallest number d, such that for any subset U⊆V where |U|=k there exists a dominating set for G of size at most d, and containing all vertices in U.