2023/06/01 by Arrepol, Francisco, Asenjo, Patricio, Astete, Raúl +6
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2306.00843
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 e1, e2 (resp. pair of vertices v1, v2) of G there is at least one path in the family that contains one of e1 and e2 (resp. v1 and v2) 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.