Target Set Selection in Cartesian product graphs

摘要

Target Set Selection (TSS) was initially proposed to study the problem of the spread of information, ideas or influence through a social network. It has formulated many problems arising in various practical applications. We consider a particular type of graphs, namely the Cartesian product, which is a classical graph structure and is widely used in the design of networking. We establish an upper bound on the k-target number mink (G square H) in terms of that of G and H for general k, which improves that of Adams' et al. In particular, a tight lower bound and a much tight upper bound for k = 2 are also given.