ON THE BALANCED DOMINATION OF GRAPHS

Let G = (V-G, E-G) be a graph and let N-G[upsilon] denote the closed neighbourhood of a vertex upsilon in G. A function f: V-G -> {-1, 0, 1} is said to be a balanced dominating function (BDF) of G if Sigma(u is an element of NG[v]) f(u) = 0 holds for each vertex upsilon is an element of V-G. The balanced domination number of G, denoted by gamma(b)(G), is defined as gamma(b)(G) = max{Sigma(v is an element of VG) f(v) : f is a BDF of G}. A graph G is called d-balanced if gamma(b)(G) = 0. The novel concept of balanced domination for graphs is introduced. Some upper bounds on the balanced domination number are established, in which one is the best possible bound and the rest are sharp, all the corresponding extremal graphs are characterized; several classes of d-balanced graphs are determined. Some open problems are proposed.