Separating path systems in trees

Abstract

For a graph $G$, an edge-separating (resp. vertex-separating) path system of $G$ is a family of paths in $G$ such that for any pair of edges $e_1,e_2$ (resp. pair of vertices $v_1,v_2$) of $G$ there is at least one path in the family that contains one of $e_1$ and $e_2$ (resp. $v_1$ and $v_2$) but not the other. We determine the size of a minimum edge-separating path system of an arbitrary tree $T$ as a function of its number of leaves and degree-two vertices. We obtain bounds for the size of a minimal vertex-separating path system for trees, which we show to be tight in many cases. We obtain similar results for a variation of the definition, where we require the path system to separate edges and vertices simultaneously. Finally, we investigate the size of a minimal vertex-separating path system in Erdős--Rényi random graphs.