Journal of Combinatorics

Volume 5 (2014)

Number 3

Separating path systems

Pages: 335 – 354

DOI: https://dx.doi.org/10.4310/JOC.2014.v5.n3.a4

Authors

Victor Falgas-Ravry (Vanderbilt University, Nashville, Tennessee, U.S.A.)

Teeradej Kittipassorn (University of Memphis, Tennessee, U.S.A.)

Dániel Korándi (Department of Mathematics, ETH Zürich, Switzerland)

Shoham Letzter (Department of Pure Mathematics and Mathematical Statistics, Centre for Mathematical Sciences, University of Cambridge, United Kingdom)

Bhargav P. Narayanan (Department of Pure Mathematics and Mathematical Statistics, Centre for Mathematical Sciences, University of Cambridge, United Kingdom)

Abstract

We study separating systems of the edges of a graph where each member of the separating system is a path. We conjecture that every $n$-vertex graph admits a separating path system of size linear in $n$ and we prove this in certain interesting special cases. In particular, we establish this conjecture for random graphs and graphs with linear minimum degree. We also obtain tight bounds on the size of a minimal separating path system in the case of trees.

Published 29 October 2014