Vertex‐Separating Path Systems in Random Graphs

ABSTRACT A set is said to be separated by subsets if, for every pair of distinct elements of , there is a set that contains exactly one of them. Imposing structural constraints on the separating subsets is often necessary for practical purposes and leads to a number of fascinating (and, in some cases, already classical) graph‐theoretic problems. In this work, we are interested in separating the vertices of a random graph by vertex sets of paths , jointly forming a separating system . First, we determine the size of the smallest separating system of when up to lower‐order terms, and exhibit a threshold phenomenon around the sharp threshold for connectivity. Second, we show that random regular graphs of sufficiently high degree can typically be optimally separated by sets. Moreover, we provide bounds for the minimum degree threshold for optimal separation of general graphs.