PreprintarXiv licencearXiv
Separating Path Systems of Size at most 7.75n
Abstract
A family of paths in a graph G strongly separates the edges of G if for every ordered pair of distinct edges (e,f) some path in the family contains e and avoids f; the minimum size of such a family is denoted by ssp(G). Bonamy, Botler, Dross, Naia, and Skokan proved, for every n-vertex graph G, that ssp(G)≤ 19n; Liu, Xu, and Yang recently improved this to ssp(G)≤ 10n−o(n). We prove, for every n-vertex graph G, that ssp(G)≤ 7.75n.
Related
- Optimal square size for separating the operator and completely bounded norms of Schur multipliers on S^4
- High-order in-cell discontinuous reconstruction path-conservative methods for conservative systems in primitive variables
- Curvature-Dependent Path Concentration in Stochastic Fast-Slow Systems with Noise on the Slow Variable
- Path space large deviation on a lattice for interacting particle systems
- Gradient flow formulation and discrete approximation of reaction-cross-diffusion systems with size exclusion
BibTeX
@misc{cranston2026separating,
title = {{Separating Path Systems of Size at most $7.75n$}},
author = {Daniel W. Cranston and Jared Noyman and Gexin Yu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.07488},
eprint = {2610.07488},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.07488},
}
RIS
TY - UNPB
TI - Separating Path Systems of Size at most 7.75n
AU - Daniel W. Cranston
AU - Jared Noyman
AU - Gexin Yu
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.07488
UR - https://arxiv.org/abs/2610.07488
AB - A family of paths in a graph G strongly separates the edges of G if for every ordered pair of distinct edges (e,f) some path in the family contains e and avoids f; the minimum size of such a family is denoted by ssp(G). Bonamy, Botler, Dross, Naia, and Skokan proved, for every n-vertex graph G, that ssp(G)≤ 19n; Liu, Xu, and Yang recently improved this to ssp(G)≤ 10n−o(n). We prove, for every n-vertex graph G, that ssp(G)≤ 7.75n.
ER -