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

Xianliang Liu, Zishen Yang and Wei Wang ()
Additional contact information
Xianliang Liu: Jiangxi University of Finance and Economics
Zishen Yang: Xi’an Jiaotong University
Wei Wang: Xi’an Jiaotong University

Journal of Combinatorial Optimization, 2021, vol. 41, issue 1, No 8, 105-117

Abstract: Abstract 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.

Keywords: Social networks; Viral marketing; Target set selection; Toroidal mesh; Toriadal cross (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00671-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:41:y:2021:i:1:d:10.1007_s10878-020-00671-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00671-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().