Geodesic
On the balanced domination of graphs
Czechoslovak Mathematical Journal, Tome 71 (2021) no. 4, pp. 933-946
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2021.0055-20
Classification : 05C69, 05C70
Keywords: domination number; balanced dominating function; balanced domination number; $d$-balanced graph 
@article{10_21136_CMJ_2021_0055_20,
     author = {Xu, Baogen and Sun, Wanting and Li, Shuchao and Li, Chunhua},
     title = {On the balanced domination of graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {933--946},
     year = {2021},
     volume = {71},
     number = {4},
     doi = {10.21136/CMJ.2021.0055-20},
     mrnumber = {4339101},
     zbl = {07442464},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0055-20/}
}
TY  - JOUR
AU  - Xu, Baogen
AU  - Sun, Wanting
AU  - Li, Shuchao
AU  - Li, Chunhua
TI  - On the balanced domination of graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2021
SP  - 933
EP  - 946
VL  - 71
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0055-20/
DO  - 10.21136/CMJ.2021.0055-20
LA  - en
ID  - 10_21136_CMJ_2021_0055_20
ER  - 
%0 Journal Article
%A Xu, Baogen
%A Sun, Wanting
%A Li, Shuchao
%A Li, Chunhua
%T On the balanced domination of graphs
%J Czechoslovak Mathematical Journal
%D 2021
%P 933-946
%V 71
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0055-20/
%R 10.21136/CMJ.2021.0055-20
%G en
%F 10_21136_CMJ_2021_0055_20
Xu, Baogen; Sun, Wanting; Li, Shuchao; Li, Chunhua. On the balanced domination of graphs. Czechoslovak Mathematical Journal, Tome 71 (2021) no. 4, pp. 933-946. doi: 10.21136/CMJ.2021.0055-20

[1] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications. Elsevier, New York (1976). | DOI | MR | JFM

[2] Caha, R., Koubek, V.: Optimal embeddings of generalized ladders into hypercubes. Discrete Math. 233 (2001), 65-83. | DOI | MR | JFM

[3] Cockayne, E. J., Mynhardt, C. M.: On a generalisation of signed dominating functions of a graphs. Ars Comb. 43 (1996), 235-245. | MR | JFM

[4] Dunbar, J., Hedetniemi, S., Henning, M. A., McRae, A.: Minus domination in graphs. Discrete Math. 199 (1999), 35-47. | DOI | MR | JFM

[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. | MR | JFM

[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). | DOI | MR | JFM

[7] Ore, O.: Theory of Graphs. American Mathematical Society Colloquium Publications 38. AMS, Providence (1962). | DOI | MR | JFM

[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. | DOI | MR | JFM

[9] Xu, B.: On signed edge domination numbers of graphs. Discrete Math. 239 (2001), 179-189. | DOI | MR | JFM

[10] Xu, B.: Two classes of edge domination in graphs. Discrete Appl. Math. 154 (2006), 1541-1546. | DOI | MR | JFM

[11] Xu, B.: On signed cycle domination in graphs. Discrete. Math. 309 (2009), 1007-1012. | DOI | MR | JFM

[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. | DOI | MR | JFM

[13] Xu, B., Zhou, S.: Characterization of connected graphs with maximum domination number. J. Math. Res. Expo. 20 (2000), 523-528. | MR | JFM

[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. | MR | JFM

Cité par Sources :