On the path separation number of graphs

A path separator of a graph G is a set of paths P={P1,…,Pt} such that for every pair of edges e,f∈E(G), there exist paths Pe,Pf∈P such that e∈E(Pe), f∉E(Pe), e∉E(Pf) and f∈E(Pf). The path separation number of G, denoted psn(G), is the smallest number of paths in a path separator. We shall estimate the path separation number of several graph families-including complete graphs, random graph, the hypercube-and discuss general graphs as well.