In this paper we study degree-penalized contact processes on Galton-Watson (GW) trees and the configuration model. The model we consider is a modification of the usual contact process on a graph. In particular, each vertex can be either infected or healthy. When infected, each vertex heals at rate one. Also, when infected, a vertex u with degree du infects its neighboring vertex v with degree d _v with rate λ/ f (d _u, d _v ) for some positive function f. In the case F (d _u, d _v = max(d _u, d _v ) ^u for some u ≥ 0, the infection is slowed down to and from high-degree vertices. This is in line with arguments used in social network science: people with many contacts do not have the time to infect their neighbors at the same rate as people with fewer contacts. We show that new phase transitions occur in terms of the parameter u (at 1/2) and the degree distribution D of the GW tree. ◦ When u ≥ 1, the process goes extinct for all distributions D for all sufficiently small λ > 0; ◦ When u E [1/2, 1), and the tail of D weakly follows a power law with tail-exponent less than 1 − u, the process survives globally but not locally for all λ small enough; ◦ When u E [1/2, 1), and E[D ^1−u] < ∞, the process goes extinct almost surely, for all λ small enough; ◦ When u < 1/2, and D is heavier than stretched exponential with stretch-exponent 1 − 2u, the process survives (locally) with positive probability for all λ > 0. We also study the product case, where f (d _u, d _v ) = (d _ud _v ) ^u. In that case, the situation for u < 1/2 is the same as the one described above, but u ≥ 1/2 always leads to a subcritical contact process for small enough λ > 0 on all graphs. Furthermore, for finite random graphs with prescribed degree sequences, we establish the corresponding phase transitions in terms of the length of survival.

A k-truncated resolving set of a graph is a subset S⊆V of its vertex set such that the vector (d_k(s,v))_s∈S is distinct for each vertex v∈V where d_k(x,y)=min⁡{d(x,y),k+1} is the graph distance truncated at k+1. We think of elements of a k-truncated resolving set as sensors that can measure up to distance k. The k-truncated metric dimension (Tmd_k) of a graph G is the minimum cardinality of a k-truncated resolving set of G. We give a sharp lower bound on Tmd_k for any tree T in terms of its number of vertices |T| and the measuring radius k. Our result is that Tmd_k(T)≥|T|⋅3/(k²+4k+3+1{k≡1(mod3)})+c_k, disproving earlier conjectures by Frongillo et al. that suspected |T|/(⌊k²/4⌋+2k)+c_k^′ as general lower bound, where c_k, c_k^′ are k-dependent constants. We provide a construction for trees with the largest number of vertices with a given Tmd_k value. The proof that our optimal construction cannot be improved relies on edge-rewiring procedures of arbitrary (suboptimal) trees with arbitrary resolving sets, which reveal the structure of how small subsets of sensors measure and resolve certain areas in the tree that we call the attraction of those sensors. The notion of ‘attraction of sensors’ might be useful in other contexts beyond trees to solve related problems. We also provide an improved lower bound on Tmd_k of arbitrary trees that takes into account the structural properties of the tree, in particular, the number and length of simple paths of degree-two vertices terminating in leaf vertices. This bound complements the result of the above-mentioned work of Frongillo et al., where only trees without degree-two vertices were considered, except the simple case of a single path.