| Title:
|
On the balanced domination of graphs (English) |
| Author:
|
Xu, Baogen |
| Author:
|
Sun, Wanting |
| Author:
|
Li, Shuchao |
| Author:
|
Li, Chunhua |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
71 |
| Issue:
|
4 |
| Year:
|
2021 |
| Pages:
|
933-946 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
domination number |
| Keyword:
|
balanced dominating function |
| Keyword:
|
balanced domination number |
| Keyword:
|
$d$-balanced graph |
| MSC:
|
05C69 |
| MSC:
|
05C70 |
| idZBL:
|
Zbl 07442464 |
| idMR:
|
MR4339101 |
| DOI:
|
10.21136/CMJ.2021.0055-20 |
| . |
| Date available:
|
2021-11-08T15:55:34Z |
| Last updated:
|
2024-01-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/149227 |
| . |
| Reference:
|
[1] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications.Elsevier, New York (1976). Zbl 1226.05083, MR 0411988, 10.1007/978-1-349-03521-2 |
| Reference:
|
[2] Caha, R., Koubek, V.: Optimal embeddings of generalized ladders into hypercubes.Discrete Math. 233 (2001), 65-83. Zbl 0986.05034, MR 1825602, 10.1016/S0012-365X(00)00227-2 |
| Reference:
|
[3] Cockayne, E. J., Mynhardt, C. M.: On a generalisation of signed dominating functions of a graphs.Ars Comb. 43 (1996), 235-245. Zbl 0881.05060, MR 1415993 |
| Reference:
|
[4] Dunbar, J., Hedetniemi, S., Henning, M. A., McRae, A.: Minus domination in graphs.Discrete Math. 199 (1999), 35-47. Zbl 0928.05046, MR 1675909, 10.1016/S0012-365X(98)00284-2 |
| Reference:
|
[5] Dunbar, J., Hedetniemi, S., Henning, M. A., Slater, P. J.: Signed domination in graphs.Graph Theory, Combinatorics, Algorithms and Applications. Vol. 1 Wiley, New York (1995), 311-321. Zbl 0842.05051, MR 1405819 |
| Reference:
|
[6] Haynes, T. W., Hedetniemi, S., Slater, P. J.: Fundamentals of Domination in Graphs.Pure and Applied Mathematics, Marcel Dekker 208. Marcel Dekker, New York (1998). Zbl 0890.05002, MR 1605684, 10.1201/9781482246582 |
| Reference:
|
[7] Ore, O.: Theory of Graphs.American Mathematical Society Colloquium Publications 38. AMS, Providence (1962). Zbl 0105.35401, MR 0150753, 10.1090/coll/038 |
| Reference:
|
[8] Wong, D., Ma, X., Tian, F.: Relation between the skew-rank of an oriented graph and the rank of its underlying graph.Eur. J. Comb. 54 (2016), 76-86. Zbl 1331.05097, MR 3459054, 10.1016/j.ejc.2015.12.005 |
| Reference:
|
[9] Xu, B.: On signed edge domination numbers of graphs.Discrete Math. 239 (2001), 179-189. Zbl 0979.05081, MR 1850997, 10.1016/S0012-365X(01)00044-9 |
| Reference:
|
[10] Xu, B.: Two classes of edge domination in graphs.Discrete Appl. Math. 154 (2006), 1541-1546. Zbl 1091.05055, MR 2222838, 10.1016/j.dam.2005.12.007 |
| Reference:
|
[11] Xu, B.: On signed cycle domination in graphs.Discrete. Math. 309 (2009), 1007-1012. Zbl 1180.05082, MR 2502161, 10.1016/j.disc.2008.01.007 |
| Reference:
|
[12] Xu, B., Cockayne, E. J., Haynes, T. W., Hedetniemi, S. T., Zhou, S.: Extremal graphs for inequalities involving domination parameters.Discrete Math. 216 (2000), 1-10. Zbl 0954.05037, MR 1750850, 10.1016/S0012-365X(99)00251-4 |
| Reference:
|
[13] Xu, B., Zhou, S.: Characterization of connected graphs with maximum domination number.J. Math. Res. Expo. 20 (2000), 523-528. Zbl 0966.05056, MR 1795416 |
| Reference:
|
[14] Zhao, Y., Shan, E., Ahangar, H. A.: Signed total domination on Kronecker products of two complete graphs.Australas. J. Comb. 56 (2013), 95-102. Zbl 1277.05133, MR 3097711 |
| . |
