The minus k-domination numbers in graphs

Document Type : Original paper


Sirjan University of Technology, Sirjan 78137, Iran


For any integer $k\ge 1$, a minus $k$-dominating function is a function $f : V \rightarrow \{-1,0, 1\}$ satisfying $\sum_{w\in N[v]} f(w)\ge k$ for every $v\in V(G)$, where $N(v) =\{u \in V(G)\mid uv\in E(G)\}$ and $N[v] =N(v)\cup \{v\}$. The minimum of the values of $\sum_{v\in V(G)}f(v)$, taken over all minus $k$-dominating functions $f$, is called the minus $k$-domination number and is denoted by $\gamma^-_{k}(G)$. In this paper, we introduce the study of minus $k$-domination in graphs and  present several sharp lower bounds on the minus $k$-domination number for general graphs.


Main Subjects

[1] M. Atapour, R. Hajypory, S.M. Sheikholeslami and L. Volkmann, The signed k-domination number of directed graphs, Cent. Eur. J. Math. 8 (2010), 1048–1057.
[2] W. Chen and E. Song, Lower bounds on several versions of signed domination number, Discrete Math. 308 (2008), 1837–1846.
[3] E.J. Cockayne and C.M. Mynhardt, On a generalization of signed dominating function of graphs, Ars Combin. 43 (1996), 235–245.
[4] D. Delić and C. Wang, Upper signed k-domination in a general graph, Inform. Process. Lett. 110 (2010), 662–665.
[5] J.E. Dunbar, S.T. Hedetniemi, M.A. Henning and A. McRae, Minus domination in graphs, Discrete Math. 199 (1999), 35–47.
[6] J.E. Dunbar, S.T. Hedetniemi, M.A. Henning and P.J. Slater, Signed domination in graphs, Graph Theory, Combinatorics, and Applications, 1 (1995), 311–322.