Disjoint Dominating Sets with a Perfect Matching

Abstract

In this paper, we consider dominating sets $D$ and $D^{\prime }$ such that $D$ and $D^{\prime }$ are disjoint and there exists a perfect matching between them. Let $D{D}_{\text{m}}(G)$ denote the cardinality of smallest such sets $D,D^{\prime }$ in $G$ (provided they exist, otherwise $D{D}_{\text{m}}(G)=\infty$). This concept was introduced in [Klostermeyer et al., Theory and Application of Graphs, 2017] in the context of studying a certain graph protection problem. We characterize the trees $T$ for which $D{D}_{\text{m}}(T)$ equals a certain graph protection parameter and for which $D{D}_{\text{m}}(T)=\alpha (T)$, where $\alpha (G)$ is the independence number of $G$. We also further study this parameter in graph products, e.g., by giving bounds for grid graphs, and in graphs of small independence number.