PreprintCC0arXiv
Strongly separating graph edges with 10n paths
Abstract
A family of paths strongly separates the edges of a graph if every two distinct edges are separated in both directions by paths in the family. Bonamy, Botler, Dross, Naia, and Skokan proved that every n-vertex graph admits such a family of at most 19n paths. We improve this bound to 10n−o(n).
Related
- Generating Functions and the Minimum Spectral Radius in Strongly Connected Digraphs with m+2 Edges
- The chromatic number of a random graph with o(n3/2) edges
- Separating Notions of Graph Width: the Adaptive, Normal, Linear, Entropic, and Submodular Width
- Every k-Quasi-Planar Graph Has Linearly Many Edges
- Third and Fourth Moment Phenomena for Monochromatic Edges and Applications to Graph-Based Two-Sample Tests
BibTeX
@misc{liu2026strongly,
title = {{Strongly separating graph edges with $10n$ paths}},
author = {Xiao-Chuan Liu and Boyan Xu and Xu Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08994},
eprint = {2609.08994},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08994},
note = {CC0},
}
RIS
TY - UNPB
TI - Strongly separating graph edges with 10n paths
AU - Xiao-Chuan Liu
AU - Boyan Xu
AU - Xu Yang
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.08994
UR - https://arxiv.org/abs/2609.08994
AB - A family of paths strongly separates the edges of a graph if every two distinct edges are separated in both directions by paths in the family. Bonamy, Botler, Dross, Naia, and Skokan proved that every n-vertex graph admits such a family of at most 19n paths. We improve this bound to 10n−o(n).
ER -