Geodesic
Separating the edges of a graph by a linear number of paths
Advances in Combinatronics (2023)

Voir la notice de l'article provenant de la source Advances in Combinatronics website

Recently, Letzter proved that any graph of order $n$ contains a collection $\mathcal{P}$ of $O(n\log^\star n)$ paths with the following property: for all distinct edges $e$ and $f$ there exists a path in $\mathcal{P}$ which contains $e$ but not $f$. We improve this upper bound to $19 n$, thus answering a question of G.O.H. 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.
Publié le : 
@article{ADVC_2023_a1,
     author = {Marthe Bonamy and F\'abio Botler and Fran\c{c}ois Dross and T\'assio Naia and Jozef Skokan},
     title = {Separating the edges of a graph by a linear number of paths},
     journal = {Advances in Combinatronics},
     publisher = {mathdoc},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ADVC_2023_a1/}
}
TY  - JOUR
AU  - Marthe Bonamy
AU  - Fábio Botler
AU  - François Dross
AU  - Tássio Naia
AU  - Jozef Skokan
TI  - Separating the edges of a graph by a linear number of paths
JO  - Advances in Combinatronics
PY  - 2023
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ADVC_2023_a1/
LA  - en
ID  - ADVC_2023_a1
ER  - 
%0 Journal Article
%A Marthe Bonamy
%A Fábio Botler
%A François Dross
%A Tássio Naia
%A Jozef Skokan
%T Separating the edges of a graph by a linear number of paths
%J Advances in Combinatronics
%D 2023
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ADVC_2023_a1/
%G en
%F ADVC_2023_a1
Marthe Bonamy; Fábio Botler; François Dross; Tássio Naia; Jozef Skokan. Separating the edges of a graph by a linear number of paths. Advances in Combinatronics (2023). http://geodesic.mathdoc.fr/item/ADVC_2023_a1/