On the p-reinforcement and the complexity

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

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

     

Profile ID: LFWR-SCP-O-411376

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.