Czechoslovak Mathematical Journal, Vol. 71, No. 4, pp. 933-946, 2021
On the balanced domination of graphs
Baogen Xu, Wanting Sun, Shuchao Li, Chunhua Li
Received February 11, 2020. Published online October 11, 2021.
Abstract: Let $G=(V_G,E_G)$ be a graph and let $N_G[v]$ denote the closed neighbourhood of a vertex $v$ in $G$. A function $f\colon V_G\rightarrow\{-1,0,1\}$ is said to be a balanced dominating function (BDF) of $G$ if $\sum_{u\in N_G[v]}f(u)=0$ holds for each vertex $v\in V_G$. The balanced domination number of $G$, denoted by $\gamma_b(G)$, is defined as $\gamma_b(G)=\max\biggl\{\sum_{v\in V_G}f(v) \colon f \text{is a BDF of} G\biggr\}.$
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.
References: [1] J. A. Bondy, U. S. R. Murty: Graph Theory with Applications. Elsevier, New York (1976). DOI 10.1007/978-1-349-03521-2 | MR 0411988 | Zbl 1226.05083
[2] R. Caha, V. Koubek: Optimal embeddings of generalized ladders into hypercubes. Discrete Math. 233 (2001), 65-83. DOI 10.1016/S0012-365X(00)00227-2 | MR 1825602 | Zbl 0986.05034
[3] E. J. Cockayne, C. M. Mynhardt: On a generalisation of signed dominating functions of a graphs. Ars Comb. 43 (1996), 235-245. MR 1415993 | Zbl 0881.05060
[4] J. Dunbar, S. Hedetniemi, M. A. Henning, A. McRae: Minus domination in graphs. Discrete Math. 199 (1999), 35-47. DOI 10.1016/S0012-365X(98)00284-2 | MR 1675909 | Zbl 0928.05046
[5] J. Dunbar, S. Hedetniemi, M. A. Henning, P. J. Slater: Signed domination in graphs. Graph Theory, Combinatorics, Algorithms and Applications. Vol. 1 Wiley, New York (1995), 311-321. MR 1405819 | Zbl 0842.05051
[6] T. W. Haynes, S. Hedetniemi, P. J. Slater: Fundamentals of Domination in Graphs. Pure and Applied Mathematics, Marcel Dekker 208. Marcel Dekker, New York (1998). DOI 10.1201/9781482246582 | MR 1605684 | Zbl 0890.05002
[7] O. Ore: Theory of Graphs. American Mathematical Society Colloquium Publications 38. AMS, Providence (1962). DOI 10.1090/coll/038 | MR 0150753 | Zbl 0105.35401
[8] D. Wong, X. Ma, F. Tian: Relation between the skew-rank of an oriented graph and the rank of its underlying graph. Eur. J. Comb. 54 (2016), 76-86. DOI 10.1016/j.ejc.2015.12.005 | MR 3459054 | Zbl 1331.05097
[9] B. Xu: On signed edge domination numbers of graphs. Discrete Math. 239 (2001), 179-189. DOI 10.1016/S0012-365X(01)00044-9 | MR 1850997 | Zbl 0979.05081
[10] B. Xu: Two classes of edge domination in graphs. Discrete Appl. Math. 154 (2006), 1541-1546. DOI 10.1016/j.dam.2005.12.007 | MR 2222838 | Zbl 1091.05055
[11] B. Xu: On signed cycle domination in graphs. Discrete. Math. 309 (2009), 1007-1012. DOI 10.1016/j.disc.2008.01.007 | MR 2502161 | Zbl 1180.05082
[12] B. Xu, E. J. Cockayne, T. W. Haynes, S. T. Hedetniemi, S. Zhou: Extremal graphs for inequalities involving domination parameters. Discrete Math. 216 (2000), 1-10. DOI 10.1016/S0012-365X(99)00251-4 | MR 1750850 | Zbl 0954.05037
[13] B. Xu, S. Zhou: Characterization of connected graphs with maximum domination number. J. Math. Res. Expo. 20 (2000), 523-528. MR 1795416 | Zbl 0966.05056
[14] Y. Zhao, E. Shan, H. A. Ahangar: Signed total domination on Kronecker products of two complete graphs. Australas. J. Comb. 56 (2013), 95-102. MR 3097711 | Zbl 1277.05133
Affiliations: Baogen Xu, Chunhua Li, School of Sciences, East China Jiaotong University, Huadong Road, Qingshanhu District, Nanchang, Jiangxi 330013, P. R. China, e-mail: baogenxu@163.com, chunhuali66@163.com; Wanting Sun, Shuchao Li (corresponding author), Faculty of Mathematics and Statistics, Central China Normal University, Road, Wuhan 430079, P. R. China, e-mail: wtsun2018@sina.com, lscmath@mail.ccnu.edu.cn
