On the path separation number of graphs

Abstract

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)$, there exist paths $P_e,P_f\in \mathcal{P}$ such that $e\in E(P_e)$, $f\notin E(P_e)$, $e\notin E(P_f)$ and $f\in E(P_f)$. The path separation number of $G$, denoted $\mathrm{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.

14 pages