×

Domination in signed graphs. (English) Zbl 1460.05079

Summary: Let \(G=(V,E)\) be a graph. A signed graph is an ordered pair \({\Sigma}=(G,\sigma)\) where \(G=(V,E)\) is a graph called the underlying graph of \({\Sigma}\) and \(\sigma:E\to\{+,-\}\) is a function called a signature or signing function. Motivated by the innovative paper of B. D. Acharya on domination in signed graphs [J. Comb. Math. Comb. Comput. 84, 5–20 (2013; Zbl 1274.05205)], we consider another way of defining the concept of domination in signed graphs which looks more natural and has applications in social science. A subset \(S\) of \(V\) is called a dominating set of \({\Sigma}\) if \(| N^+(v)\cap S|>| N^-(v)\cap S|\) for all \(v\in V-S\). The domination number of \({\Sigma}\), denoted by \(\gamma_s({\Sigma})\), is the minimum cardinality of a dominating set of \({\Sigma} \). Also, a dominating set \(S\) of \({\Sigma}\) with \(|S|= \gamma_s\) is called a \(\gamma_s\)-set of \({\Sigma} \). In this paper, we initiate a study on this parameter.

MSC:

05C22 Signed and weighted graphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Citations:

Zbl 1274.05205
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] B. D. Acharya, Domination and absorbence in signed graph and digraph: I. Foundations, to appear in J. Combin. Inform. Syst. Sci.
[2] Anitha, A., Arumugam, S. and Chellali, M., Equitable domination in graphs, Discrete Math. Algorithms Appl.3(3) (2011) 311-321. · Zbl 1243.05181
[3] Chartrand, G. and Lesniak, L., Graphs and Digraphs, 4th edn. (CRC Press, 2005). · Zbl 1057.05001
[4] Haynes, T. W., Hedetniemi, S. T. and Slater, P. J., Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). · Zbl 0890.05002
[5] Haynes, T. W., Hedetniemi, S. T. and Slater, P. J., Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998). · Zbl 0883.00011
[6] Sudev, N. K., Chithra, K. P. and Germina, K. A., Switched signed graphs of integer additive set-valued signed graphs, Discrete Math. Algorithms Appl.9(4) (2017) 1750043. · Zbl 1373.05169
[7] Zaslavsky, T., Signed graphs, Discrete Appl. Math.4 (1982) 47-74. · Zbl 0476.05080
[8] Zaslavsky, T., A mathematical bibliography of signed and gain graphs and allied areas. VII Edition, Electron. J. Combin.8 (1998) 124, Dynamic surveys 8. · Zbl 0898.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.