Domination and Absorbance in Signed Graphs And Digraphs: I. Foundations

Abstract

A signed graph (digraph) $\mathrm{\Sigma }$ is an ordered triple $(V,E,\sigma )$ (respectively, $(V,\mathcal{A},\sigma )$), where $|\mathrm{\Sigma }|:=(V,E)$ (respectively, $(V,\mathcal{A})$) is a graph (digraph), called the underlying graph (underlying digraph) of $\mathrm{\Sigma }$, and $\sigma$ is a function that assigns to each edge (arc) of $|\mathrm{\Sigma }|$ a weight $+1$ or $-1$. Any edge (arc) $e$ of $\mathrm{\Sigma }$ is said to be positive or negative according to whether $\sigma (e)=+1$ or $\sigma (e)=-1$. A subset $D\subseteq V$ of vertices of $\mathrm{\Sigma }$ is an absorbent (respectively, a dominating set) of $\mathrm{\Sigma }$ if there exists a marking $\mu :V\to \{+1,-1\}$ of $\mathrm{\Sigma }$ such that every vertex $u$ of $\mathrm{\Sigma }$ is either in $D$ or
$$O(u)\cap D\ne \mathrm{\varnothing }\text{and}\sigma (u,v)=\mu (u)\mu (v)\mathrm{\forall }v\in O(u)\cap D,$$
(respectively,
$$I(u)\cap D\ne \mathrm{\varnothing }\text{and}\sigma (u,v)=\mu (u)\mu (v)\mathrm{\forall }v\in I(u)\cap D),$$
where $O(u)$ ($I(u)$) denotes the set of vertices $v$ of $\mathrm{\Sigma }$ that are joined by the outgoing arcs $(u,v)$ from $u$ (incoming arcs $(v,u)$ at $u$). Further, an absorbent (dominating set) of $\mathrm{\Sigma }$ that is independent is called a kernel (solution) of $\mathrm{\Gamma }$. The main aim of this paper is to initiate a study of absorbents and dominating sets in a signed graph (signed digraph), extending the existing studies on these special sets of vertices in a graph (digraph).