On the p-reinforcement and the complexity

Details On the p-reinforcement and the complexity On the p-reinforcement and the complexity

2012-04-18

arxiv.org/abs/1204.4013v1

Mathematics

Combinatorics

17 pages, 22 references

Scientific paper

Let $G=(V,E)$ be a graph and $p$ be a positive integer. A subset $S\subseteq V$ is called a $p$-dominating set if each vertex not in $S$ has at least $p$ neighbors in $S$. The $p$-domination number $\g_p(G)$ is the size of a smallest $p$-dominating set of $G$. The $p$-reinforcement number $r_p(G)$ is the smallest number of edges whose addition to $G$ results in a graph $G'$ with $\g_p(G')<\g_p(G)$. In this paper, we give an original study on the $p$-reinforcement, determine $r_p(G)$ for some graphs such as paths, cycles and complete $t$-partite graphs, and establish some upper bounds of $r_p(G)$. In particular, we show that the decision problem on $r_p(G)$ is NP-hard for a general graph $G$ and a fixed integer $p\geq 2$.

Affiliated with

Also associated with

No associations

Rating

On the p-reinforcement and the complexity 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 p-reinforcement and the complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the p-reinforcement and the complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-411376