On the integer {k}-domination number of circulant graphs

Abstract

Let $G=(V,E)$ be a simple undirected graph. $G$ is a circulant graph defined on $V={\mathbb{Z}}_n$ with difference set $D\subseteq \{1,2,\dots ,\lfloor \frac{n}{2}\rfloor \}$ provided two vertices $i$ and $j$ in ${\mathbb{Z}}_n$ are adjacent if and only if $\min \{|i-j|,n-|i-j|\}\in D$. For convenience, we use $G(n;D)$ to denote such a circulant graph. A function $f:V(G)\to \mathbb{N}\cup \{0\}$ is an integer $\{k\}$-domination function if for each $v\in V(G)$, ${\sum }_{u\in N_G[v]}f(u)\ge k.$ By considering all $\{k\}$-domination functions $f$, the minimum value of ${\sum }_{v\in V(G)}f(v)$ is the $\{k\}$-domination number of $G$, denoted by ${\hat{I}}_k^3(G)$. In this paper, we prove that if $D=\{1,2,\dots ,t\}$, $1\le t\le \frac{n-1}{2}$, then the integer $\{k\}$-domination number of $G(n;D)$ is $\lceil \frac{kn}{2t+1}\rceil$.