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 (nu) = inverted right perpendicular rho d(v) inverted left perpendicular, where rho (0, 1) and d (v) denotes the degree of the vertex v (is an element of V), a subset S subset of V is called a strong target set if for each vertex v. 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.

Automated summary

This paper discusses the problem of finding a t-latency bounded strong target set with minimum cardinality in a given simple graph G. By proposing an inequality and specifying certain conditions, exact formulas for optimal solutions were derived.