On the Distance Paired-Domination of Circulant Graphs

Haoli Wang ; Xirong Xu ; Yuansheng Yang ; Guoqing Wang ; Kai Lü

Bulletin of the Malaysian Mathematical Society, Tome 34 (2011) no. 1

Résumé

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}$

Détail

Classification : 05C69, 05C12.