Characterization of signed paths and cycles admitting minus dominating function

Document Type : Original paper


Department of Mathematics, CHRIST (Deemed to be University), Bangalore-29, INDIA


Let $G=(V,E,\sigma)$ be a finite signed graph. A function $f: V \rightarrow\{-1,0,1\}$ is a minus dominating function (MDF) of $ G $ if $f(u)+\sum_{v \in N(u)} \sigma (uv)f(v)\geq 1 $ for all $ u\in V $. In this paper we characterize signed paths and cycles admitting an MDF.


Main Subjects

[1] B.D. Acharya, Minus domination in signed graphs, Journal of Combinatorics, Information and System Sciences 37 (2012), 333–358.
[2] D. Cartwright and F. Harary, Structural balance: a generalization of heider’s theory., Psych. Rev. 63 (1956), no. 5, 277–293.
[3] J. Dunbar, S. Hedetniemi, M.A. Henning, and A. McRae, Minus domination in graphs, Discrete Math. 199 (1999), no. 1-3, 35–47.
[4] F. Harary, On the notion of balance of a signed graph, Mich. Math. J. 2 (1953), no. 2, 143–146.