On the Signed (Total) $k$-Domination Number of a Graph

Details On the Signed (Total) $k$-Domination Number of a Graph On the Signed (Total) $k$-Domination Number of a Graph

2012-04-21

arxiv.org/abs/1204.4827v1

Computer Science

Discrete Mathematics

Accepted by JCMCC

Scientific paper

Let $k$ be a positive integer and $G=(V,E)$ be a graph of minimum degree at least $k-1$. A function $f:V\rightarrow \{-1,1\}$ is called a \emph{signed $k$-dominating function} of $G$ if $\sum_{u\in N_G[v]}f(u)\geq k$ for all $v\in V$. The \emph{signed $k$-domination number} of $G$ is the minimum value of $\sum_{v\in V}f(v)$ taken over all signed $k$-dominating functions of $G$. The \emph{signed total $k$-dominating function} and \emph{signed total $k$-domination number} of $G$ can be similarly defined by changing the closed neighborhood $N_G[v]$ to the open neighborhood $N_G(v)$ in the definition. The \emph{upper signed $k$-domination number} is the maximum value of $\sum_{v\in V}f(v)$ taken over all \emph{minimal} signed $k$-dominating functions of $G$. In this paper, we study these graph parameters from both algorithmic complexity and graph-theoretic perspectives. We prove that for every fixed $k\geq 1$, the problems of computing these three parameters are all \NP-hard. We also present sharp lower bounds on the signed $k$-domination number and signed total $k$-domination number for general graphs in terms of their minimum and maximum degrees, generalizing several known results about signed domination.

Affiliated with

Also associated with

No associations

Rating

On the Signed (Total) $k$-Domination Number of a Graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Signed (Total) $k$-Domination Number of a Graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Signed (Total) $k$-Domination Number of a Graph will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-729515