$\gamma'$-Realizability and Other Musings on Inverse Domination

Abstract

We introduce and study $\gamma'$-realizable sequences. For a finite, simple graph $G$ containing no isolated vertices, $I \subseteq V(G)$ is said to be an \emph{inverse dominating set} if $I$ dominates all of $G$ and $I$ is contained by the complement of some minimum dominating set $D$. Define a sequence of positive integers $(x_1, \ldots , x_n)$ to be \emph{$\gamma'$-realizable} if there exists a graph $G$ having exactly $n$ distinct minimum dominating sets $D_1, \ldots, D_n$ where for each $i \in \{1, \ldots, n\}$, the minimum size of an inverse dominating set in $V(G) \setminus D_i$ is equal to $x_i$. In this work, we show which sequences having minimum entry 2 or less are $\gamma'$-realizable. We then detail a few observations and results arising during our investigations that may prove useful in future research.

Keywords

• inverse domination
• realizability