ON THE BALANCED DOMINATION OF GRAPHS

作者：Xu, Baogen; Sun, Wanting; Li, Shuchao^*; Li, Chunhua

来源：CZECHOSLOVAK MATHEMATICAL JOURNAL, 2021, 71(4): 933-946.

DOI：10.21136/CMJ.2021.0055-20

• domination number
• balanced dominating function
• balanced domination number
• d-balanced graph

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 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.