Spreading in graphs
Discrete Applied Mathematics · 2024-08 · 353 · 139-150
DOI: 10.1016/j.dam.2024.04.019 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Applied Mathematics, 2024-08. Verfasst von Boštjan Brešar und 3 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 23 Literaturangaben. Gefördert von: ARRS.
Abstract (Originalsprache)
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, $\sigma_{(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\in \mathbb{N}$ and $q\in\mathbb{N}\cup\{\infty\}$, 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 $\sigma_{(p,q)}(P_m\Box P_n)$ for all $(p,q)\in (\mathbb{N}\setminus\{3\})\times (\mathbb{N}\cup\{\infty\})$ and all $m,n\in\mathbb{N}$.
Förderung
- ARRS
Zitieren
APA
Brešar, B., Dravec, T., Erey, A., & Hedžet, J. (2024). Spreading in graphs. Discrete Applied Mathematics, 353, 139-150. https://doi.org/10.1016/j.dam.2024.04.019
Vancouver
Brešar B, Dravec T, Erey A, Hedžet J. Spreading in graphs. Discrete Applied Mathematics. 2024;353:139-150. doi:10.1016/j.dam.2024.04.019
BibTeX
@article{Brear2024,
author = {Brešar, Boštjan and Dravec, Tanja and Erey, Aysel and Hedžet, Jaka},
title = {Spreading in graphs},
journal = {Discrete Applied Mathematics},
year = {2024},
volume = {353},
pages = {139--150},
doi = {10.1016/j.dam.2024.04.019}
}
EUVIMED