Unique Independence, Upper Domination and Upper Irredundance in Graphs

Abstract

A set $D$ of vertices in a graph $G$ is irredundant if every vertex $v$ in $D$ has at least one private neighbour in $N[v,G]\setminus N[D\setminus \{v\},G]$. A set $D$ of vertices in a graph $G$ is a minimal dominating set of $G$ if $D$ is irredundant and every vertex in $V(G)\setminus D$ has at least one neighbour in $D$. Further, irredundant sets and minimal dominating sets of maximal cardinality are called $IR$-sets and $\mathrm{\Gamma }$-sets, respectively. A set $I$ of the vertex set of a graph $G$ is independent if no two vertices in $I$ are adjacent, and independent sets of maximal cardinality are called $\alpha$-sets.

In this paper, we prove that bipartite graphs and chordal graphs have a unique $\alpha$-set if and only if they have a unique $\mathrm{\Gamma }$-set if and only if they have a unique $IR$-set. Some related results are also presented.