EUVIMEDEUVIMED entdecken
Crossref

Spreading in graphs

Boštjan Brešar, Tanja Dravec, Aysel Erey, Jaka Hedžet

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.

AbstractBibliografische AngabenZitieren

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}
}
Kostenlos starten →