On the balanced domination of graphs

Baogen Xu; Wanting Sun; Shuchao Li; Chunhua Li

Czechoslovak Mathematical Journal (2021)

  • Volume: 71, Issue: 4, page 933-946
  • ISSN: 0011-4642

Abstract

top
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 : V G → { - 1 , 0 , 1 } is said to be a balanced dominating function (BDF) of G if ∑ u ∈ N G [ v ] f ( u ) = 0 holds for each vertex v ∈ V G . The balanced domination number of G , denoted by γ b ( G ) , is defined as γ b ( G ) = max ∑ v ∈ V G f ( v ) : f is a BDF of G . A graph G is called d -balanced if γ 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.

How to cite

top

Xu, Baogen, et al. "On the balanced domination of graphs." Czechoslovak Mathematical Journal 71.4 (2021): 933-946. <http://eudml.org/doc/298230>.

@article{Xu2021,
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 \lbrace -1,0,1\rbrace $ 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 \lbrace \sum \_\{v\in V\_G\}f(v) \colon f\ \text\{is a BDF of\}\ G\biggr \rbrace . \] 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.},
author = {Xu, Baogen, Sun, Wanting, Li, Shuchao, Li, Chunhua},
journal = {Czechoslovak Mathematical Journal},
keywords = {domination number; balanced dominating function; balanced domination number; $d$-balanced graph},
language = {eng},
number = {4},
pages = {933-946},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On the balanced domination of graphs},
url = {http://eudml.org/doc/298230},
volume = {71},
year = {2021},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 71
IS - 4
SP - 933
EP - 946
AB - 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 \lbrace -1,0,1\rbrace $ 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 \lbrace \sum _{v\in V_G}f(v) \colon f\ \text{is a BDF of}\ G\biggr \rbrace . \] 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.
LA - eng
KW - domination number; balanced dominating function; balanced domination number; $d$-balanced graph
UR - http://eudml.org/doc/298230
ER -

References

top
  1. Bondy, J. A., Murty, U. S. R., 10.1007/978-1-349-03521-2, Elsevier, New York (1976). (1976) Zbl1226.05083MR0411988DOI10.1007/978-1-349-03521-2
  2. Caha, R., Koubek, V., 10.1016/S0012-365X(00)00227-2, Discrete Math. 233 (2001), 65-83. (2001) Zbl0986.05034MR1825602DOI10.1016/S0012-365X(00)00227-2
  3. Cockayne, E. J., Mynhardt, C. M., On a generalisation of signed dominating functions of a graphs, Ars Comb. 43 (1996), 235-245. (1996) Zbl0881.05060MR1415993
  4. Dunbar, J., Hedetniemi, S., Henning, M. A., McRae, A., 10.1016/S0012-365X(98)00284-2, Discrete Math. 199 (1999), 35-47. (1999) Zbl0928.05046MR1675909DOI10.1016/S0012-365X(98)00284-2
  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. (1995) Zbl0842.05051MR1405819
  6. Haynes, T. W., Hedetniemi, S., Slater, P. J., 10.1201/9781482246582, Pure and Applied Mathematics, Marcel Dekker 208. Marcel Dekker, New York (1998). (1998) Zbl0890.05002MR1605684DOI10.1201/9781482246582
  7. Ore, O., 10.1090/coll/038, American Mathematical Society Colloquium Publications 38. AMS, Providence (1962). (1962) Zbl0105.35401MR0150753DOI10.1090/coll/038
  8. Wong, D., Ma, X., Tian, F., 10.1016/j.ejc.2015.12.005, Eur. J. Comb. 54 (2016), 76-86. (2016) Zbl1331.05097MR3459054DOI10.1016/j.ejc.2015.12.005
  9. Xu, B., 10.1016/S0012-365X(01)00044-9, Discrete Math. 239 (2001), 179-189. (2001) Zbl0979.05081MR1850997DOI10.1016/S0012-365X(01)00044-9
  10. Xu, B., 10.1016/j.dam.2005.12.007, Discrete Appl. Math. 154 (2006), 1541-1546. (2006) Zbl1091.05055MR2222838DOI10.1016/j.dam.2005.12.007
  11. Xu, B., 10.1016/j.disc.2008.01.007, Discrete. Math. 309 (2009), 1007-1012. (2009) Zbl1180.05082MR2502161DOI10.1016/j.disc.2008.01.007
  12. Xu, B., Cockayne, E. J., Haynes, T. W., Hedetniemi, S. T., Zhou, S., 10.1016/S0012-365X(99)00251-4, Discrete Math. 216 (2000), 1-10. (2000) Zbl0954.05037MR1750850DOI10.1016/S0012-365X(99)00251-4
  13. Xu, B., Zhou, S., Characterization of connected graphs with maximum domination number, J. Math. Res. Expo. 20 (2000), 523-528. (2000) Zbl0966.05056MR1795416
  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. (2013) Zbl1277.05133MR3097711

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.