2023/09/28 by Brešar, Boštjan, Dravec, Tanja, Erey, Aysel +1 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2309.16852
Several concepts that model processes of spreading (of information, disease, objects, etc.) in graphs or networks have been studied. In many contexts, we assume that some vertices of a graph G are contaminated initially, before the process starts. By the q-forcing rule, a contaminated vertex having at most q uncontaminated neighbors enforces all the neighbors to become contaminated, while by the p-percolation rule, an uncontaminated vertex becomes contaminated if at least p of its neighbors are contaminated. In this paper, we consider sets S that are at the same time q-forcing sets and p-percolating sets, and call them (p,q)-spreading sets. Given positive integers p and q, the minimum cardinality of a (p,q)-spreading set in G is a (p,q)-spreading number, σ(p,q)(G), of G. While q-forcing sets have been studied in a dozen of papers, the decision version of the corresponding graph invariant has not been considered earlier, and we fill the gap by proving its NP-completeness. This, in turn, enables us to prove the NP-completeness of the decision version of the (p,q)-spreading number in graphs for an arbitrary choice of p and q. Again, for every p∈ ℕ and q∈ℕ∪\∞\, we find a linear-time algorithm for determining the (p,q)-spreading number of a tree. In addition, we present a lower and an upper bound on the (p,q)-spreading number of a tree and characterize extremal families of trees. In the case of square grids, we combine some known results and new results on (2,1)-spreading and (4,q)-spreading to obtain σ(p,q)(Pm\Box Pn) for all (p,q)∈ (ℕ∖\3\)× (ℕ∪\∞\) and all m,n∈ℕ.