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.

The “random intersection graph with communities” (RIGC) models networks with communities, assuming an underlying bipartite structure of groups and individuals. Each group has its own internal structure described by a (small) graph, while groups may overlap. The group memberships are generated by a bipartite configuration model. The model generalizes the classical random intersection graph model, a special case where each community is a complete graph. The RIGC model is analytically tractable. We prove a phase transition in the size of the largest connected component in terms of the model parameters. We prove that percolation on RIGC produces a graph within the RIGC family, also undergoing a phase transition with respect to size of the largest component. Our proofs rely on the connection to the bipartite configuration model. Our related results on the bipartite configuration model are of independent interest, since they shed light on interesting differences from the unipartite case.

Random intersection graphs model networks with communities, assuming an underlying bipartite structure of communities and individuals, where these communities may overlap. We generalize the model, allowing for arbitrary community structures within the communities. In our new model, communities may overlap, and they have their own internal structure described by arbitrary finite community graphs. Our model turns out to be tractable. We analyze the overlapping structure of the communities, show local weak convergence (including convergence of subgraph counts), and derive the asymptotic degree distribution and the local clustering coefficient.