Separating the edges of a graph by a linear number of paths

DOI10.19086/AIC.2023.6MaRDI QIDQ6423970FDOQ6423970

Authors Marthe Bonamy, F. Botler, François Dross, Tássio Naia, J. Skokan 

Publication date 20 January 2023

Abstract: Recently, Letzter proved that any graph of order $n$ contains a collection $mathcalP$ of $O(nlo{g}^{s}tarn)$ paths with the following property: for all distinct edges $e$ and $f$ there exists a path in $mathcalP$ which contains $e$ but not $f$. We improve this upper bound to $19n$, thus answering a question of Katona and confirming a conjecture independently posed by Balogh, Csaba, Martin, and Pluh'ar and by Falgas-Ravry, Kittipassorn, Kor'andi, Letzter, and Narayanan. Our proof is elementary and self-contained.

This page was built for publication: Separating the edges of a graph by a linear number of paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6423970)