A Contribution to Upper Domination, Irredundance and Distance-2 Domination in Graphs

Abstract

Let $G=(V,E)$ be a graph. The open neighborhood of a vertex $v\in V$ is the set $N(v)=\{u\mid uv\in E\}$ and the closed neighborhood of $v$ is the set $N[v]=N(v)\cup \{v\}$. The open neighborhood of a set $S$ of vertices is the set $N(S)=\bigcup _{v\in S}N(v)$, while the closed neighborhood of a set $S$ is the set $N[S]=\bigcup _{v\in S}N[v]$. A set $S\subset V$ dominates a set $T\subset V$ if $T\subseteq N[S]$, written $S\to T$. A set $S\subset V$ is a dominating set if $N[S]=V$; and is a minimal dominating set if it is a dominating set, but no proper subset of $S$ is also a dominating set; and is a $\gamma$-set if it is a dominating set of minimum cardinality. In this paper, we consider the family $\mathcal{D}$ of all dominating sets of a graph $G$, the family $\mathcal{M}\mathcal{D}$ of all minimal dominating sets of a graph $G$, and the family $\mathrm{\Gamma }$ of all $\gamma$-sets of a graph $G$. The study of these three families of sets provides new characterizations of the distance-2 domination number, the upper domination number, and the upper irredundance number in graphs.