Target set selection problem for honeycomb networks

Details Target set selection problem for honeycomb networks Target set selection problem for honeycomb networks

2012-03-03

arxiv.org/abs/1203.0666v1

Computer Science

Discrete Mathematics

Scientific paper

Let $G$ be a graph with a threshold function $\theta:V(G)\rightarrow \mathbb{N}$ such that $1\leq \theta(v)\leq d_G(v)$ for every vertex $v$ of $G$, where $d_G(v)$ is the degree of $v$ in $G$. Suppose we are given a target set $S\subseteq V(G)$. The paper considers the following repetitive process on $G$. At time step 0 the vertices of $S$ are colored black and the other vertices are colored white. After that, at each time step $t>0$, the colors of white vertices (if any) are updated according to the following rule. All white vertices $v$ that have at least $\theta(v)$ black neighbors at the time step $t-1$ are colored black, and the colors of the other vertices do not change. The process runs until no more white vertices can update colors from white to black. The following optimization problem is called Target Set Selection: Finding a target set $S$ of smallest possible size such that all vertices in $G$ are black at the end of the process. Such an $S$ is called an {\em optimal target set} for $G$ under the threshold function $\theta$. We are interested in finding an optimal target set for the well-known class of honeycomb networks under an important threshold function called {\em strict majority threshold}, where $\theta(v)=\lceil (d_G(v)+1)/2\rceil$ for each vertex $v$ in $G$. In a graph $G$, a {\em feedback vertex set} is a subset $S\subseteq V(G)$ such that the subgraph induced by $V(G)\setminus S$ is cycle-free. In this paper we give exact value on the size of the optimal target set for various kinds of honeycomb networks under strict majority threshold, and as a by-product we also provide a minimum feedback vertex set for different kinds regular graphs in the class of honeycomb networks

Affiliated with

Also associated with

No associations

Rating

Target set selection problem for honeycomb networks 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 Target set selection problem for honeycomb networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Target set selection problem for honeycomb networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-345719