Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
domination number; balanced dominating function; balanced domination number; $d$-balanced graph
domination number; balanced dominating function; balanced domination number; $d$-balanced graph
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.
References:
[1] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications. Elsevier, New York (1976). DOI 10.1007/978-1-349-03521-2 | MR 0411988 | Zbl 1226.05083
[2] Caha, R., Koubek, V.: 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] Cockayne, E. J., Mynhardt, C. M.: On a generalisation of signed dominating functions of a graphs. Ars Comb. 43 (1996), 235-245. MR 1415993 | Zbl 0881.05060
[4] Dunbar, J., Hedetniemi, S., Henning, M. A., McRae, A.: Minus domination in graphs. Discrete Math. 199 (1999), 35-47. DOI 10.1016/S0012-365X(98)00284-2 | MR 1675909 | Zbl 0928.05046
[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 1405819 | Zbl 0842.05051
[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 10.1201/9781482246582 | MR 1605684 | Zbl 0890.05002
[7] Ore, O.: Theory of Graphs. American Mathematical Society Colloquium Publications 38. AMS, Providence (1962). DOI 10.1090/coll/038 | MR 0150753 | Zbl 0105.35401
[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 10.1016/j.ejc.2015.12.005 | MR 3459054 | Zbl 1331.05097
[9] Xu, B.: 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] Xu, B.: 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] Xu, B.: 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] 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 10.1016/S0012-365X(99)00251-4 | MR 1750850 | Zbl 0954.05037
[13] Xu, B., Zhou, S.: Characterization of connected graphs with maximum domination number. J. Math. Res. Expo. 20 (2000), 523-528. MR 1795416 | Zbl 0966.05056
[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 3097711 | Zbl 1277.05133
Search
Partner of
