On domination in signed graphs

Abstract

In this article the concept of domination in signed graphs is examined from an alternate perspective and a new definition of the same is introduced. A vertex subset D of a signed graph S is a dominating set, if for each vertex v not in D there exists a vertex u ∈ D such that the sign of the edge uv is positive. The domination number γ (S) of S is the minimum cardinality among all the dominating sets of S. We obtain certain bounds of γ (S) and present a necessary and su cient condition for a dominating set to be a minimal dominating set. Further, we characterise the signed graphs having small and large values for domination number.

Keywords

• signed graphs
• dominating set
• domination number
• minimal dominating set