1 Introduction

Social networks, as a major scientific object, have attracted more attention from researchers. One type of typical problems considered by many scholars is how to spread influence through a social network, such as promoting novel ideas, marketing new products, or spreading innovation. Domingos and Richardson (2001) initially proposed the influential nodes selection problem in social networks. Kempe et al. (2015, 2005) further formulated the influential nodes selection problem as an optimization problem which is called influence maximization problem is how to select k nodes in the network which generate the largest expected cascade based on a given probabilistic diffusion model. They presented a natural greedy algorithm that achieves a performance ratio of \(1-\frac{1}{e}-\varepsilon \) for any \(\varepsilon >0\).

The target set selection (TSS) problem was considered by Chen (2009) that is how to find a small set S of nodes to influence the entire network. He proved a strong inapproachability result that there exists no algorithm for it with approximation factor better than \(O(2^{\log ^{1- \varepsilon }|V|})\). Subsequently, Ben-Zwi et al. (2011) proved that the TSS problem can be solved in time \(n^{O(\omega )}\), but not in \(n^{o(\sqrt{\omega })}\) unless all problems in SNP can be solved in sub-exponential time, where \(\omega \) is the treewidth of a graph. In addition, a combinatorial lower and upper bounds on the size of the minimum perfect TSS problem was proposed by Ackerman et al. (2010). An improved bound was founded by Chang and Lyuu (2010) for majority thresholds in directed graphs. The TSS problem and it’s variants have also been studied in references Chopin et al. (2014); Chiang et al. (2013, 2011, 2013); Flocchini et al. (2003); Khoshkhah et al. (2012); Karimi and Holme (2013); Nichterlein et al. (2013); Zhang et al. (2012); Zaker (2012); Dinh et al. (2012).

An important variant of TSS problem is the t-latency bounded target set selection (t-LBTSS) problem which is how to find the smallest nodes to influence the entire networks in t rounds. Peleg (2002) showed that this problem is a NP-hardness problem. Zou et al. (2009) gave two heuristic algorithms in the case of \(t=1\). Dinh et al. (2012) proved that any feasible solution to the t-LBTSS problem is a constant factor approximation for power-law graphs. Cicalese et al. (2014) gave a polynomial time exact algorithm for graphs with bounded clique-width and pointed out that Chen’s inapproximability result still holds for the t-LBTSS problem. A tight lower bound in terms of the sum degrees of any feasible solution to the t-LBTSS problem was proposed by Liu et al. (2013).

In this paper, we consider a variant of the t-LBTSS problem named the t-Latency Bounded Strong Target Set Selection (t-LBSTSS) problem which is formally described as follows.

Let a simple graph \(G=(V,E)\) be a social network, and a positive integer t be a latency bound. For any vertex v, assume that the threshold \(\theta (v)=\lceil \rho d(v) \rceil \), where \(\rho \in (0,1)\) is a rational number and d(v) is the degree of v. Initially, all vertices in V are inactive. Then a vertex subset \(S(\subseteq V)\) is selected which satisfies that each vertex \(v(\in S)\) has at least \(\lceil \rho d(v) \rceil \) neighbors in S and only the vertices in S is activated. For convenience, the vertex subset S is usually denoted by \(A_0\). For any integer \(i(1\le i\le t)\), assume that \(A_1,A_2,\cdots ,A_{i-1}\) represent the subsets of vertices which have been activated at the rounds \(1,2,\cdots ,i-1\), respectively. A vertex v is activated at the ith round if and only if \(v\in V{\setminus }\cup _{0\le j<i}A_j\) and it has at least \(\lceil \rho d(v)\rceil \) neighbors in \(\cup _{0\le j<i}A_j\). The subset of all such vertices activated at the ith round is denoted by \(A_i\). The subset \(S(\subseteq V)\) is called a strong target set if all vertices in V are activated after t rounds. The t-LBSTSS problem is to find a strong target set S with smallest cardinality.

In what follows, the cardinality of an optimal solution to the t-LBSTSS problem is denoted by \(\mathrm {min\text {-}LBSTSS}(G,\rho ,t)\). Moreover, the threshold \(\theta (v)=\lceil \rho d(v)\rceil \) is called majority threshold if \(\rho =\frac{1}{2}\). The main innovations and contributions of this work are highlighted as follows:

  1. (1)

    For any strong target set S to the t-LBSTSS problem, the sum of degrees of S is lower bounded by some constant factor of the number of edges in any given graph through a simple, tight and nontrivial inequality. In addition, a necessary and sufficient condition for the equality to hold is given.

  2. (2)

    Based on the inequality, we are able to give a method to construct families of infinite number of graphs for which the optimal solution to the t-LBTSS problem becomes apparent.

  3. (3)

    The exact formulas for the optimal solutions to the t-LBSTSS problem in two kinds of natural family of graphs are presented and proven using the inequality.

2 The inequality

For the t-LBSTSS problem, it is difficult to find its exact or even approximate optimal solution in general graph. In this section, an important inequality is proposed to measure it indirectly, namely, the sum of degrees of any strong target set S is lower bounded by some constant factor of the number of edges in the given graph.

To simplify the description, it is necessary to give some notations in what follows. For any given graph \(G=(V,E)\), denote by \(d_A(v)\) the number of neighbors of a vertex v in a vertex subset A, namely, \(d_A(v)=|N(v)\cap A|\), where N(v) represents all the neighbors of v in graph G. Let \(d_A(B)\) be the sum of degrees of the vertex subset B in the induced subgraph G[A]. It means that \(d_A(B)=\sum _{v\in B}d_A(v)\). Specially, the notation d(B) indicates the sum of degrees of the subset B in the graph G, i.e., \(d(B)=\sum _{v\in B}d(v)\). The subset of edges between two vertex subsets A and B is denoted by E(A, B), namely, \(E(A,B)=\{(u,v)\in E|u\in A~\text {and}~v\in B\}\). Let E(A) be the set of edges in the induced subgraph G[A]. If there exists no confusion, the vertex subset A represents the vertex set itself or its corresponding induced subgraph G[A]. According to the above notations, it is not difficult to find that \(|E(A,B)|=d_A(B)=d_B(A)\). Now, an important theorem is presented and proven as follows.

Theorem 1

For any graph \(G=(V,E)\), a latency bound \(t\in {\mathbb {N}}^+\) and active coefficient \(\rho \in (0,1)\), the sum of degrees of any strong target set S to the t-LBSTSS problem satisfies the following inequality

$$\begin{aligned} d(S)&\ge \frac{2\rho ^t}{\displaystyle \sum _{i=0}^t\rho ^i(1-\rho )^{t-i}} \cdot |E|=\left\{ \begin{array}{ll} \displaystyle \frac{2\rho ^t(2\rho -1)}{\rho ^{t+1}-(1-\rho )^{t+1}}\cdot |E|, &{}\displaystyle \rho \in (0,\frac{1}{2})\cup (\frac{1}{2},1) \\ \displaystyle \frac{2}{t+1}\cdot |E|, &{}\displaystyle \rho =\frac{1}{2} \end{array} \right. \end{aligned}$$

where \(d(S)=\sum _{v\in S}d(v)\) and |E| is the number of edges in the graph G.

Proof

Let \(A_i\) be the subset of vertices activated by S at the ith round, \(1\le i\le t\). For convenience, the strong target set S is also denoted by \(A_0\), i.e., \(A_0=S\). For any \(i=0,1,\cdots ,t\), we define that \(U_i:=\bigcup _{j=0}^iA_j\) and \({\overline{U}}_i:=V{\setminus } U_i\) in what follows.

According to the definition of the strong target set S to the t-LBSTSS problem, it is not difficult to discover that

$$\begin{aligned} d_S(v)\ge \lceil \rho d(v)\rceil \ge \rho d(v) \end{aligned}$$
(1)

for each vertex \(v\in S\). Summing up Eq. (1) for all vertices \(v\in S\), the inequality can be obtained as follows:

$$\begin{aligned} 2|E(S)|=|E(S,S)|\ge \rho d(S). \end{aligned}$$
(2)

In addition, according to the condition of the activation , it is not a tough work to gain that

$$\begin{aligned} d_{U_{i-1}}(v)\ge \lceil \rho d(v)\rceil \ge \rho d(v) \end{aligned}$$
(3)

for any vertex \(v\in A_i\). Similarly, summing up Eq. (3) for all vertices \(v\in A_i\) gives that

$$\begin{aligned} |E(U_{i-1},A_i)|\ge \rho d(A_i). \end{aligned}$$
(4)

for any \(i=1,2,\cdots ,t.\)

Next, for any \(i=1,2,\cdots ,t\), it is easy to see by a counting argument that \(d(U_{i-1})\) satisfies the following equation:

$$\begin{aligned} d(U_{i-1})&=|E(U_{i-1},U_{i-1})|+|E(U_{i-1},A_i)| +|E(U_{i-1},{\overline{U}}_i)| \\&= 2|E(U_{i-1})|+|E(U_{i-1},A_i)|+|E(U_{i-1},{\overline{U}}_i)| \nonumber \end{aligned}$$
(5)

where

$$\begin{aligned} |E(U_{i-1})|=\sum _{j=0}^{i-1}|E(A_j)| +\sum _{j=1}^{i-1}|E(U_{j-1},A_j)|. \end{aligned}$$
(6)

It follows from Eqs. (4)–(6) that

$$\begin{aligned} d(U_{i-1})\ge 2\sum _{j=0}^{i-1}|E(A_j)|+2\rho \sum _{j=1}^{i-1}d(A_j) +\rho d(A_i)+|E(U_{i-1},\overline{U_i})|, \end{aligned}$$

where

$$\begin{aligned} \sum _{j=0}^{i-1}|E(A_j)|\ge |E(S)| \end{aligned}$$
(7)

and

$$\begin{aligned} |E(U_{i-1},{\overline{U}}_i)|\ge 0. \end{aligned}$$
(8)

Hence,

$$\begin{aligned} d(U_{i-1})\ge&2|E(S)| +2\rho \sum _{j=1}^{i-1}d(A_j) +\rho d(A_i)\\&\ge \rho d(S)+2\rho (d(U_{i-1})-d(U_0))+\rho (d(U_i)-d(U_{i-1}))\\&=\rho d(U_i)+\rho d(U_{i-1})-\rho d(S). \end{aligned}$$

Namely,

$$\begin{aligned} \rho d(S)\ge \rho d(U_i)-(1-\rho )d(U_{i-1}) \end{aligned}$$
(9)

for any \(i=1,2,\cdots ,t.\)

Multiplying by \(\rho ^{i-1}(1-\rho )^{t-i}\) (\(>0\)) on both sides of Eq. (9) and summing up all inequalities for \(i=1,2,\cdots ,t\), it is not difficult to discover that most of the terms on the right side cancel out. Thus, the following inequality can be obtained:

$$\begin{aligned} \bigg ((1-\rho )^t+\sum _{i=1}^t\rho ^i(1-\rho )^{t-i}\bigg ) d(S)\ge \rho ^t d(U_t)=\rho ^t d(V)=2\rho ^t|E|. \end{aligned}$$

Therefore, it yields that

$$\begin{aligned} d(S)\ge \frac{2\rho ^t|E|}{\displaystyle \sum _{i=0}^t\rho ^i(1-\rho )^{t-i}}. \end{aligned}$$

Due to the following equality holds:

$$\begin{aligned} \sum _{i=0}^t\rho ^i(1-\rho )^{t-i} =\left\{ \begin{array}{ll} \displaystyle \frac{\rho ^{t+1}-(1-\rho )^{t+1}}{2\rho -1}, &{}\displaystyle \rho \in (0,1){\setminus }\Big \{\frac{1}{2}\Big \}\\ \displaystyle \frac{t+1}{2^t}, &{}\displaystyle \rho =\frac{1}{2} \end{array} \right. , \end{aligned}$$

the sum of degrees of the strong target set S satisfies the following inequality:

$$\begin{aligned} \mathrm {d}(S)\ge \left\{ \begin{array}{ll} \displaystyle \frac{2\rho ^t(2\rho -1)}{\rho ^{t+1}-(1-\rho )^{t+1}}\cdot |E|, &{}\displaystyle \rho \in (0,\frac{1}{2})\cup (\frac{1}{2},1) \\ \displaystyle \frac{2}{t+1}\cdot |E|, &{}\displaystyle \rho =\frac{1}{2} \end{array} \right. . \end{aligned}$$

This completes the proof. \(\square \)

In fact, the inequality in Theorem 1 is tight. In the following, the conditions are considered for which the equality in Theorem 1 holds.

Theorem 2

For any graph \(G=(V,E)\), a subset S of V is a strong target set to the t-LBSTSS problem and the equality in Theorem 1 holds if and only if the following conditions hold simultaneously:

  1. (i)

    \(A_0,A_1,\cdots ,A_t\) is a vertex division of V. All edges of graph G are either between \(A_j\) and \(A_j\) \((j\in \{0,t\})\) or between \(A_{i-1}\) and \(A_i\) \((i=1,2,\cdots ,t)\). Namely,

    $$\begin{aligned} E=\big (\cup _{j=0,t}E(A_j)\big )\bigcup \big (\cup _{i=1}^tE(A_{i-1},A_i)\big ). \end{aligned}$$
    (10)
  2. (ii)

    \(d_S(v)=\rho d(v)\), \(\forall v\in S\) and \(d_{A_{i-1}}(v)=\rho d(v)\), \(\forall v\in A_i\), \(i=1,2,\cdots ,t\).

Proof

First, let’s verify the sufficient part of the theorem. According to condition (ii), it is easy to see that \(S=A_0\) must be a feasible solution to the t-LBSTSS problem. The next task is only to show that the equality in Theorem 1 must hold under the conditions (i) and (ii).

Summing up all the equations in condition (ii), one has

$$\begin{aligned} \begin{array}{ccc} 2|E(S)|=\rho d(S)&\quad \text {and}&\quad |E(A_{i-1},A_i)|=\rho d(A_i),\quad \forall i=1,2,\cdots ,t. \end{array} \end{aligned}$$

Thus, by the condition (i), the following equations is established:

$$\begin{aligned} d(A_0)=2|E(A_0)|+|E(A_0,A_1)|=\rho \cdot d(A_0)+\rho \cdot d(A_1), \end{aligned}$$

and

$$\begin{aligned} d(A_{i-1})=|E(A_{i-2},A_{i-1})|+|E(A_{i-1},A_i)| =\rho \cdot d(A_{i-1})+\rho \cdot d(A_i) \end{aligned}$$

for \(i=2,3,\cdots ,t.\)

It follows that

$$\begin{aligned} (1-\rho )\cdot d(A_{i-1})=\rho \cdot d(A_i), \quad \forall ~i=1,2,\cdots ,t. \end{aligned}$$

That is to say, the following equations hold:

$$\begin{aligned} d(A_i)=\frac{1-\rho }{\rho }\cdot d(A_{i-1})=\cdots =(\frac{1-\rho }{\rho })^{i}\cdot d(A_0) \end{aligned}$$

for \(i=1,2,\cdots ,t.\)

Note that \(2|E|=d(U_t)=\sum _{0\le i\le t} d(A_i)\), i.e.,

$$\begin{aligned}&2|E|=\sum _{i=0}^t(\frac{1-\rho }{\rho })^{i}\cdot d(A_0)\\&=\frac{\rho ^{t}+(1-\rho )\rho ^{t-1}+(1-\rho )^2\rho ^{t-2} +\dots +(1-\rho )^{t}}{\rho ^t}\cdot d(A_0). \end{aligned}$$

Thus, the sufficiency part is true.

Next, we illustrate that the necessary part of the theorem is also true. Obviously, \(A_0,A_1,\cdots ,A_t\) is a vertex division of V because S is a strong target set of G. According to the Proof of Theorem 1, the equality holds in the conclusion of Theorem 1 if and only if all equalities hold in the Proof of Theorem 1. Therefore, the equalities also hold in Eqs.(7) and (8) for \(i=1,2,\cdots ,t\). Thus, it yields that

$$\begin{aligned} E(A_i)=\varnothing , \quad \forall i=1,2,\cdots ,t-1, \end{aligned}$$

and

$$\begin{aligned} E(A_i,A_j)=\varnothing , \quad \forall 0\le i\le t, i+2\le j\le t. \end{aligned}$$

That is to say, Eq. (10) holds in condition (i).

Similarly, the left sides are exact equal to the right sides in both Eqs. (2) and (4) ( also in Eqs. (1) and (3)). Namely,

$$\begin{aligned} d_S(v)=\rho d(v),~ \forall v\in S \end{aligned}$$

and

$$\begin{aligned} d_{U_{i-1}}(v)=\rho d(v),~\forall v\in A_i,i=1,2,\cdots ,t, \end{aligned}$$

which implies that the condition (ii) holds. This completes the proof. \(\square \)

In the next section, some applications are exhibited for which the optimal solutions to the t-LBSTSS problem can be perfectly obtained in some natural family of graphs according to Theorems 1 and 2.

3 Some applications

In this section, the main task is to present the optimal solutions to the t-LBSTSS problem in two kinds of natural family of graph by the above theorems.

Based on the inequality in Theorem 1, in the following Theorem 3, we give an explicit construction of infinite number of graphs for which the equality holds, and hence the optimal solutions to the t-LBSTSS problem become obvious on these graphs.

Theorem 3

Let \(\rho \in (0,1)\) be a rational number and t be a positive integer. Assume that \(d_0, d_1, \cdots , d_t\) are positive integers such that \(\rho d_i\) are integers for \(i=0,1,\cdots ,t\) and \(d_0\) is the largest. If \(G=(V,E)\) is a graph with vertex division \(V=\cup _{i=0}^tV_i\) and satisfies the following properties:

  • All edges in G are either between \(V_j\) and \(V_j\)\((j\in \{0,t\})\) or between \(V_{i-1}\) and \(V_i\) \((i=1,2,\cdots ,t)\). Namely,

    $$\begin{aligned}E=E(V_0)\cup E(V_t)\cup \bigcup _{i=1}^tE(V_{i-1},V_i). \end{aligned}$$

  • G is partitioned regular, i.e., all the vertices in \(V_i\) have the same degree:

    $$\begin{aligned} d(v)=d_i,\forall v\in V_i,\quad i=0,1,\cdots ,t. \end{aligned}$$

  • The degrees of vertices in \(V_i\) \((i=0,1,\cdots ,t)\) satisfy that

    $$\begin{aligned} d_{V_0}(v)=\rho d_0,\forall v\in V_0 ~~\text {and}~~ d_{V_{i-1}}(v)=\rho d_i,\forall v\in V_i,~i=1,2,\cdots ,t. \end{aligned}$$

Then \(V_0\) is an optimal solution to the t-LBSTSS problem for graph G.

Proof

Obviously, if \(V_0\) is selected and only the vertices in \(V_0\) become activated, then all the vertices in \(V_i\) can be activated at the ith round for \(i=0,1,\cdots ,t\). Therefore, \(V_0\) is a strong target set of graph G.

Owing to the following equation holds:

$$\begin{aligned} (1-\rho )d_{i-1}|V_{i-1}|=|E(V_{i-1},V_i)|=\rho d_i|V_i| \end{aligned}$$

for \(i=1,2,\cdots ,t\), it follows that

$$\begin{aligned} d(V_i)=d_i|V_i|=\Big (\frac{1-\rho }{\rho }\Big )^id_0|V_0| =\frac{(1-\rho )^i}{\rho ^i}\cdot d(V_0), \quad i=0,1,\cdots ,t. \end{aligned}$$

In addition, we have

$$\begin{aligned} 2|E|=d(V)=\sum _{i=0}^td(V_i) =\sum _{i=0}^t\frac{(1-\rho )^i}{\rho ^i}\cdot d(V_0). \end{aligned}$$

It yields that

$$\begin{aligned} \mathrm {min\text {-}LBSTSS}(G,\rho ,t)\ge \frac{\rho ^t}{\displaystyle \sum _{i=0}^t\rho ^i(1-\rho )^{t-i}} \cdot \frac{2|E|}{\Delta (G)} =\frac{d(V_0)}{d_0}=|V_0|. \end{aligned}$$

That is to say, \(V_0\) must be an optimal solution to the t-LBSTSS problem for graph G. \(\square \)

In the following, we give the optimal solutions to the t-LBSTSS problem in two kinds of natural family of graphs, which seems difficult to tell what the optimal solutions are for these graphs without using the equality given in Theorem 1.

The toroidal mesh of size \(m\times n\) denoted by \(C_m\square C_n\) is defined as the Cartesian product of two cycles \(C_m\) and \(C_n\). An example \(C_{10}\square C_5\) is shown in Fig. 1. Furthermore, p dimensional toroidal mesh \(C_{L_1}\square C_{L_2}\square \cdots \square C_{L_p}\) (\(L_1,L_2,\cdots ,L_p\in {\mathbb {N}}^+\)) is defined as the Cartesian product of p cycles and can also be rewritten as \(\square _{i=1}^pC_{L_i}\). It is noteworthy that the treewidth of toroidal mesh is unbounded by literature Diestel (2005); Kaminski et al. (2009).

Fig. 1
figure 1

Toroidal Mesh \(C_{10}\square C_5\)

Full size image

Theorem 4

(Toroidal Mesh) Let \(G=C_m\square C_n\) be a toroidal mesh with \((2t+2)|\gcd (m,n)\), where t, m, n are positive integers. Then

$$\begin{aligned} \mathrm {min\text {-}LBSTSS}(G,\frac{1}{2},t) =\frac{mn}{t+1}. \end{aligned}$$

Proof

Denote the vertices in two cycles \(C_m\) and \(C_n\) by \(u_1,u_2,\cdots ,u_m=u_0\) and \(v_1,v_2,\cdots ,v_n=v_0\), respectively. For convenience, let \(u_{i-1}u_i\) and \(v_{j-1}v_j\) be the edges in \(C_m\) and \(C_n\) for \(i=1,2,\cdots ,m; j=1,2,\cdots ,n\), respectively. According to the definition of Cartesian product, we have

$$\begin{aligned}V(G)=\Big \{(u_i,v_j)\Big |1\le i\le m,1\le j\le n\Big \},\end{aligned}$$

and

$$\begin{aligned} E(G)=\Big \{(u_{i_1},v_{j_1})(u_{i_2},v_{j_2})\Big |&u_{i_1}=u_{i_2}\in V(C_m)~\text{ and }~v_{j_1}v_{j_2}\in E(C_n)\\ ~\text{ or }~~&v_{j_1}=v_{j_2}\in V(C_n)~\text{ and }~u_{i_1}u_{i_2}\in E(C_m)\Big \}. \end{aligned}$$

Obviously, G is a 4-regular graph. Therefore, a vertex subset S can be selected as follows:

$$\begin{aligned} S=\Big \{(u_i,v_j)\Big |(2t+2)|(i+j)~\text {or}~(2t+2)|(i+j+1)\Big \} _{0\le i\le m, 0\le j\le n}. \end{aligned}$$

Then, the following characters can be checked one by one:

  • S satisfies the condition: \(d_S(v)=\rho d(v)\), \(\forall v\in S\).

  • The activated vertex subset at the lth round

    $$\begin{aligned} A_l=\Big \{(u_i,v_j)\Big |(2t+2)|(i+j-l) ~\text {or}~(2t+2)|(i+j+l+1)\Big \}, \quad l=1,2,\cdots ,t. \end{aligned}$$

  • \(A_0=S,A_1,\cdots ,A_t\) is a division of the vertex set V.

  • The equality holds in Theorem 1. Namely, \(\displaystyle d(S)=\frac{4mn}{t+1}\).

The above characters show that the vertex subset S is an optimal solution to the t-LBSTSS problem by Theorem 3. Therefore, it follows that

$$\begin{aligned} \mathrm {min\text {-}LBSTSS}(G,\frac{1}{2},t)=\frac{d(S)}{4}=\frac{mn}{t+1}. \end{aligned}$$

\(\square \)

Actually, the conclusion is also true in the cycle and high dimensional toroidal mesh.

Theorem 5

(p Dimensional Toroidal Mesh) Let p be a positive integers and \(G=\square _{i=1}^pC_{L_i}\) be a p dimensional toroidal mesh with \((2t+2)\big |L_i(i=1,2,\cdots ,p)\), then we have

$$\begin{aligned} \mathrm {min\text {-}LBSTSS}(G,\frac{1}{2},t)=\frac{\prod _{i=1}^pL_i}{t+1}. \end{aligned}$$

Proof

Denote the vertices in cycle \(C_{L_i}\) by \(v_i^1,v_i^2,\cdots ,v_i^{L_i}=v_i^0(i=1,2,\cdots ,p)\). For convenience, assume that the edges in \(C_{L_i}\) are \(v_i^{j_i}v_i^{j_i+1}\) for \(j_i=0,1,\cdots ,L_i-1\). According to the definition of Cartesian product, we have

$$\begin{aligned} V(G)=\Big \{(v_1^{j_1},v_2^{j_2},\cdots ,v_p^{j_p})\Big | j_k=1,2,\cdots ,L_k,~k=1,2,\cdots ,p\Big \}, \end{aligned}$$

and

$$\begin{aligned} E(G)=\Big \{&(x_1,x_2,\cdots ,x_p)(y_1,y_2,\cdots ,y_p) \Big |\exists r\in \{1,2,\cdots ,p\},\\&~\text {s.t.}~x_ry_r\in E(C_r),\forall q\in \{1,2,\cdots ,p\}{\setminus }\{r\},x_q=y_q\in V(C_q)\Big \}. \end{aligned}$$

Clearly, p dimensional toroidal mesh G is a regular graph with all vertices degree 2p. Thus, a vertex subset S of V can be selected as follows:

$$\begin{aligned} S=\Big \{(v_1^{j_1},v_2^{j_2},\cdots ,v_p^{j_p})\Big | (2t+2)\big |\sum _{i=1}^pj_i ~~\text {or}~~ (2t+2)\big |\sum _{i=1}^pj_i+1\Big \}_{0\le j_k\le L_k,~k=1,2,\cdots ,p} \end{aligned}$$

Set

$$\begin{aligned} A_l=&\Big \{(v_1^{j_1},v_2^{j_2},\cdots ,v_p^{j_p}) \Big |(2t+2)\big |(\sum _{i=1}^pj_i-l) ~~\text {or}~~ (2t+2)\big |(\sum _{i=1}^pj_i+l+1)\Big \}, \end{aligned}$$

then \(A_l\) is the activated vertex subset by S at the lth round, where \(l=0,1,\cdots ,t\).

Similarly, it can be proven that S is an optimal solution to the t-LBSTSS problem with

$$\begin{aligned}|S|=\frac{\prod _{i=1}^pL_i}{t+1}.\end{aligned}$$

This completes the proof. \(\square \)

Besides toriadal mesh generated by the Cartesian product of finite cycles, Theorem 1 can help us to find the optimal solutions in lots of graphs. In the following, we show that there does exist other natural family of graphs in which the optimal solutions to the t-LBSTSS problem can be obtained using the equality given in Theorem 1.

Definition 1

(Tensor Product) The tensor product of two graphs G and H denoted by \(G\times H\) refers to the graph whose vertex set is the Cartesian product of V(G) and V(H), and the edge set consists of \((u_1,v_1)(u_2,v_2)\) which \(u_1u_2\) and \(v_1v_2\) are edges in G and H, respectively. Namely,

  • \(V(G\times H)=V(G)\times V(H)\);

  • \(E(G\times H)=\{(u_1,v_1)(u_2,v_2)|u_1u_2\in E(G) ~\text {and}~v_1v_2\in E(H)\}\).

According to the definition, it is not difficult to discover that the tensor product of two graphs satisfies the communication law and the association law. Thus, it is proper to define tensor product of finite graphs as \(\times _{i=1}^pG_i=G_1\times G_2\times \cdots \times G_p\), where \(G_1\), \(G_2\), \(\cdots \), \(G_p\) are graphs. The toriadal cross is exact the graph generated by the tensor product of finite cycles. An example of the toriadal cross \(C_6\times C_4\) is shown in Fig. 2.

Fig. 2
figure 2

Toriadal cross \(C_6\times C_4\)

Full size image

The following theorems can provide a method to find the optimal solutions to the t-LBSTSS problem in toriadal crosses.

Theorem 6

Let \(G=\times _{i=1}^pC_{L_i}\) be a p dimensional toriadal cross with \((2t+2)\big |L_i(i=1,2,\cdots ,p)\). Then

$$\begin{aligned} \mathrm {min\text {-}LBSTSS}(G,\frac{1}{2},t)=\frac{\prod _{i=1}^pL_i}{t+1}. \end{aligned}$$

Proof

Denote the vertices in cycle \(C_{L_i}\) by \(v_i^1,v_i^2,\cdots ,v_i^{L_i}=v_i^0(i=1,2,\cdots ,p)\). For convenience, assume that the edges in \(C_{L_i}\) are \(v_i^{j_i}v_i^{j_i+1}(j_i=0,1,\cdots ,L_i-1)\). According to the definition of tensor product, the vertex set V(G) and the edge set E(G) of G can be expressed, respectively as

$$\begin{aligned} V(G)=\Big \{(v_1^{j_1},v_2^{j_2},\cdots ,v_p^{j_p})\Big | j_k=1,2,\cdots ,L_k,~k=1,2,\cdots ,p\Big \}, \end{aligned}$$

and

$$\begin{aligned} E(G)=\Big \{&(x_1,x_2,\cdots ,x_p)(y_1,y_2,\cdots ,y_p) \Big |x_ky_k\in E(C_k),~k=1,2,\cdots ,p\Big \}. \end{aligned}$$

Obviously, G is a regular graph with all vertices degree \(2^p\). Thus, a vertex subset S of V(G) is selected as follows:

$$\begin{aligned} S=\Big \{(v_1^{j_1},v_2^{j_2},\cdots ,v_p^{j_p})\Big | (2t+2)\big |j_p ~~\text {or}~~ (2t+2)\big |j_p+1\Big \}_{0\le j_k\le L_k,~k=1,2,\cdots ,p}. \end{aligned}$$

Set

$$\begin{aligned} A_l=&\Big \{(v_1^{j_1},v_2^{j_2},\cdots ,v_p^{j_p}) \Big |(2t+2)\big |(j_p-l) ~~\text {or}~~ (2t+2)\big |(j_p+l+1)\Big \}, \end{aligned}$$

then \(A_l\) is the activated vertex subset by S at the lth round, where \(l = 0,1,\cdots ,t\).

According to the symmetry of the tensor product, it can also be proven that S is an optimal solution to the t-LBSTSS problem with

$$\begin{aligned} |S|=\frac{\prod _{i=1}^pL_i}{t+1}. \end{aligned}$$

This completes the proof. \(\square \)

4 Conclusion and future work

In this paper, a simple, tight but nontrivial inequality is proposed that the sum of degrees of any strong target set to the t-LBSTSS problem is lower bounded by some constant factor of the number of edges in the given graph. Based on the inequality, we give a method to construct families of infinite number of graphs for which the optimal solution to the t-LBTSS problem becomes apparent. The exact formulas are presented for the optimal solutions to the t-LBSTSS problem in two kinds of natural family of graphs.

In the future, the optimal solutions to the t-LBSTSS problem will be further investigated in more kinds of natural families of graphs.