Abstract.
Let \(G=(V,E)\) be a graph without isolated vertices. A set \(D\subseteq V\) is a \(d\)-distance paired-dominating set of \(G\) if \(D\) is a \(d\)-distance dominating set of \(G\) and the induced subgraph \(G=(V,E)\) has a perfect matching. The minimum cardinality of a \(d\)-distance paired-dominating set for graph \(G\) is the \(d\)-distance paired-domination number, denoted by \(\gamma_p^{d}(G)\). In this paper, we study the \(d\)-distance paired-domination number of circulant graphs \(C(n;\{1,k\})\) for \(2\leq k\leq 4\). We prove that for \(k=2\), \(n\geq 5\) and \(d\geq 1\),
\[\gamma_p^{d}(C(n;\{1,k\}))=2\left\lceil \frac{n}{2kd+3}\right\rceil,\]
for \(k=3\), \(n\geq 7\) and \(d\geq 1\),
\[\gamma_p^{d}(C(n;\{1,k\}))=2\left\lceil \frac{n}{2kd+2}\right\rceil,\]
and for \(k=4\) and \(n\geq 9\),
(i) if \(d=1\), then
\[\begin{array}{llll} \gamma_p(C(n;\{1,k\}))= \left\{\begin{array}{llll} 2\lceil \frac{3n}{23}\rceil+2, & \mbox{if } n\equiv 15,22 \mbox{ (mod } 23); \\
2\lceil \frac{3n}{23}\rceil, & \mbox{otherwise } \\ \end{array} \right . \end{array}\]
(ii) if \(d\geq 2\), then
\[\begin{array}{llll} \gamma_p^{d}(C(n;\{1,k\}))= \left\{\begin{array}{llll} 2\lceil \frac{2n}{4kd+1}\rceil+2, & \mbox{if } n\equiv 2kd,4kd-1,4kd\\& \mbox{ (mod } 4kd+1)\\
2\lceil \frac{2n}{4kd+1}\rceil, & \mbox{otherwise. } \\ \end{array} \right. \end{array}\]
2010 Mathematics Subject Classification: 05C69, 05C12.
