The t-latency bounded strong target set selection problem in some kinds of special family of graphs

For a given simple graph \(G=(V,E)\), a latency bound t and a threshold function \(\theta (v)=\lceil \rho d(v)\rceil \), where \(\rho \in (0,1)\) and d(v) denotes the degree of the vertex \(v(\in V)\), a subset \(S\subseteq V\) is called a strong target set if for each vertex \(v\in S\), the number of its neighborhood in S not including itself is at least \(\theta (v)\), and all vertices in V can be activated by S through a process with t rounds. Initially, all vertices in S become activated. At the ith round of the process, each vertex is activated if the number of active vertices in its neighbor after \(i-1\) rounds exceeds its threshold. The \(t\)-Latency Bounded Strong Target Set Selection (t-LBSTSS) problem is to find such a strong target set S with the minimum cardinality in G. In general graphs, the t-LBSTSS problem is not only NP-hard, but also hard to be approximated. The aim of this paper is to find an optimal t-latency bounded strong target set for some special family of graphs. For a given simple graph G, a simple, tight but nontrivial inequality in terms of the number of edges in G is proposed to obtain the lower bound of the sum of degrees in a strong target set S to the t-LBSTSS problem. Moreover, a necessary and sufficient condition is presented for equality to hold. Finally, we give the exact formulas for the optimal solutions to the t-LBSTSS problem in two kinds of natural family of graphs, while it seems difficult to tell without the inequality given in this paper.