# Target set selection problem for honeycomb networks

Research paper by **Chun-Ying Chiang, Liang-Hao Huang, Hong-Gwa Yeh**

Indexed on: **03 Mar '12**Published on: **03 Mar '12**Published in: **Computer Science - Discrete Mathematics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

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