γ-paired dominating graphs of cycles

Abstract

A paired dominating set of a graph $G$ is a dominating set whose induced subgraph contains a perfect matching. The paired domination number, denoted by $\gamma_{pr}(G)$, is the minimum cardinality of a paired dominating set of $G$. A $\gamma_{pr}(G)$-set is a paired dominating set of cardinality $\gamma_{pr}(G)$. The $\gamma$-paired dominating graph of $G$, denoted by $PD_{\gamma}(G)$, as the graph whose vertices are $\gamma_{pr}(G)$-sets. Two $\gamma_{pr}(G)$-sets $D_1$ and $D_2$ are adjacent in $PD_{\gamma}(G)$ if there exists a vertex $u \in D_{1}$ and a vertex $v \notin D_{1}$ such that $D_2=(D_1\setminus \{u\})\cup \{v\}$. In this paper, we present the $\gamma$-paired dominating graphs of cycles.