Global minus domination in graphs

Document Type : Research Paper

Authors

1 University of Bonab

2 Azarbaijan Shahid Madani University

Abstract

‎A function $f:V(G)\rightarrow \{-1,0,1\}$ is a minus‎ ‎dominating function if for every vertex $v\in V(G)$‎, ‎$\sum_{u\in‎ ‎N[v]}f(u)\ge 1$‎. ‎A minus dominating function $f$ of $G$ is called‎ ‎a global minus dominating function if $f$ is also a minus‎ ‎dominating function of the complement $\overline{G}$ of $G$‎. ‎The‎ global minus domination number $\gamma_{g}^-(G)$ of $G$ is‎ ‎defined as $\gamma_{g}^-(G)=\min\{\sum_{v\in V(G)} f(v)\mid f‎ ‎\;{\rm is\; a\; global\; minus\; dominating\; function}\\ {\rm of‎ ‎}\; G\}$‎. ‎In this paper we initiate the study of the global minus ‎domination number in graphs and we establish lower and upper‎ ‎bounds for the global minus domination number‎.

Keywords

Main Subjects


S. Arumugam, I. S. Hamid and K. Karuppasamy (2010). Fractional global domination in graphs. Discuss. Math. Graph Theory. 30, 33-44 M. Atapour, S. M. Sheikholeslami and L. Volkmann Global Roman domination in graphs. Graphs Combin., (to appear). M. Atapour, S. M. Sheikholeslami and A. Khodkar (2011). Global signed total domination in graphs. Publ. Math. Debrecen. 79, 7-22 R. C. Brigham and R. D. Dutton (1990). Factor domination in graphs. Discrete Math.. 86, 127-136 E. J. Cockayne and C. M. Mynhardt (1996). On a generalisation of signed dominating functions of a graph. Ars Combin.. 43, 235-245 P. Damaschke (2001). Minus domination in small-degree graphs. Discrete Appl. Math.. 108, 53-64 D. Deliacutec and C. P. Wang The global connected domination in graphs. Ars Combin., (to appear). J. Dunbar, S. Hedetniemi, M. A. Henning and A. McRae (1999). Minus domination in graphs. Discrete Math.. 199, 35-47 J. Dunbar, S. Hedetniemi, M. A. Henning and A. McRae (1996). Minus domination in regular graphs. Discrete Math.. 149, 311-312 J. Dunbar, S. T. Hedetniemi, M. A. Henning and P. J. Slater (1995). Signed domination in graphs. Graph Theory, Combinatorics, and algorithms, Wiley, New York. 1,2, 311-321 O. Favaron (1996). Signed domination in regular graphs. Discrete Math.. 158, 287-293 Z. Furedi and D. Mubayi (1999). Signed domination in regular graphs and set-systems. J. Combin. Theory Ser. B. 76, 223-239 J. H. Hattingh, M. A. Henning and P. J. Slater (1995). The algorithmic complexity of signed domination in graphs. Australas. J. Combin.. 12, 101-112 T. W. Haynes, S. T. Hedetniemi, P. J. Slater and (Eds.) (1998). Domination in Graphs: Advanced Topics. Marcel Dekker, New York. H. Karami, R. Khoeilar, S. M. Sheikholeslami and A. Khodkar (2013). Global signed domination in graphs. Bull. Malays. Math. Sci. Soc.(2). 36, 363-372 V. R. Kulli and B. Janakiram (1996). The total global domination number of a graph. India J. Pure Appl. Math.. 27, 537-542 E. Sampathkumar (1989). The global domination number of a graph. J. Math. Phy. Sci.. 23, 377-385 M. Y. Sohn, J. Leey and Y. S. Kwon (2004). Lower bounds of signed domination number of a graph. Bull. Korean Math. Soc.. 41, 181-188 D. B. West (1996). Introduction to Graph Theory. Prentice-Hall, Inc.. V. Zverovich and A. Poghosyan (2011). On Roman, global and restrained domination in graphs. Graphs Combin.. 27, 755-768