Minimum Contagious Sets in Trees with Degree-Proportional Thresholds

@misc{choi2026minimum,
  title = {{Minimum Contagious Sets in Trees with Degree-Proportional Thresholds}},
  author = {Jeong-Ok Choi and Collin McDevitt},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.35745},
  eprint = {2610.35745},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.35745},
}

TY  - UNPB
TI  - Minimum Contagious Sets in Trees with Degree-Proportional Thresholds
AU  - Jeong-Ok Choi
AU  - Collin McDevitt
PY  - 2026
DA  - 2026/10/26
PB  - arXiv
DO  - 10.48550/arxiv.2610.35745
UR  - https://arxiv.org/abs/2610.35745
AB  - We investigate how large the minimum size of a contagious set can be among trees of a fixed order. Given a graph G and ρ∈[0,1], an inactive vertex u becomes active when at least ⌈ρd_G(u)⌉ of its neighbors are active. An initial set of active vertices is contagious if the process eventually activates every vertex. We obtain exact values for the minimum size of a contagious set in perfect d-ary trees. We then determine the exact maximum of this minimum size over all trees of order n. We establish this result by bounding the number of pairwise disjoint resistant sets, each of which must intersect every contagious set, and constructing trees that attain the resulting bounds. Finally, by bounding the change in the minimum size of a contagious set under a leaf exchange, we show that, for 0<ρ≤1 and n≥2, every integer between $1$ and this maximum occurs as the minimum size of a contagious set in a tree of order n.
ER  -