On the path separation number of graphs

A path separator of a graph $G$ is a set of paths $\mathcal{P}=\{P_1,\dots ,P_t\}$ such that for every pair of edges $e,f\in E(G)$,thereexistpaths$P_e,P_f\in$\mathcal{P}$$suchthat$e\in E(P_e)$,$f\not\in E(P_e)$,$e\not\in E(P_f)$and$f\in E(P_f)$. The path separation number of $G$, denoted $\mathrm{p}\mathrm{s}\mathrm{n}(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.