Minimum Contagious Sets in Trees with Degree-Proportional Thresholds
We investigate how large the minimum size of a contagious set can be among trees of a fixed order. Given a graph $G$ and $ρ\in[0,1]$, an inactive vertex $u$ becomes active when at least $\lceil{ρd_G(u)\rceil}$ 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,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.35745
curl -X POST /api/v1/records/arxiv/2610.35745/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.35745/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'