MAXIMUM NUMBER OF EDGES IN CONNECTED GRAPHS WITH A GIVEN DOMINATION NUMBER

A dominating set for graph G = (V, E) is a subset of vertices V' subset-or-is-equal-to V such after that for all upsilon is-a-member-of V - V', there exists some u is-a-member-of V' for which {upsilon, u} is-a-member-of E. The domination number of G is the size of its smallest dominating set(s). In this paper we give an upper bound on the number of edges a connected graph with a given number of vertices and a given domination number can have. We also characterize the extremal graphs attaining this upper bound.