Fair domination in graphs

A fair dominating set in a graph G (or FD-set) is a dominating set S such that all vertices not in Sate dominated by the same number of vertices from S; that is, every two vertices not in S has the same number of neighbors in S. The fair domination number, fd(G), of G is the minimum cardinality of an FD-set. Among other results, we show that if G is a connected graph of order n >= 3 with no isolated vertex, then fd(G) <= n - 2, and we construct an infinite family of connected graphs achieving equality in this bound. We show that if G is a maximal outerplanar graph, then fd(G) < 17n/19. If T is a tree of order n >= 2, then we prove that fd(T) <= n/2 with equality if and only if T is the corona of a tree. (C) 2012 Elsevier B.V. All rights reserved.