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)$$ G = ( V , E ) , a latency bound t and a threshold function $$\theta (v)=\lceil \rho d(v)\rceil $$ θ ( v ) = ⌈ ρ d ( v ) ⌉ , where $$\rho \in (0,1)$$ ρ ∈ ( 0 , 1 ) and d(v) denotes the degree of the vertex $$v(\in V)$$ v ( ∈ V ) , a subset $$S\subseteq V$$ S ⊆ V is called a strong target set if for each vertex $$v\in S$$ v ∈ S , the number of its neighborhood in S not including itself is at least $$\theta (v)$$ θ ( 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$$ i - 1 rounds exceeds its threshold. The $$t$$ 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.