| Autor: |
Arrepol, Francisco, Asenjo, Patricio, Astete, Raúl, Cartes, Víctor, Gajardo, Anahí, Henríquez, Valeria, Opazo, Catalina, Sanhueza-Matamala, Nicolás, Caro, Christopher Thraves |
| Rok vydání: |
2023 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
For a graph $G$, an edge-separating (resp. vertex-separating) path system of $G$ is a family of paths in $G$ such that for any pair of edges $e_1, e_2$ (resp. pair of vertices $v_1, v_2$) of $G$ there is at least one path in the family that contains one of $e_1$ and $e_2$ (resp. $v_1$ and $v_2$) but not the other. We determine the size of a minimum edge-separating path system of an arbitrary tree $T$ as a function of its number of leaves and degree-two vertices. We obtain bounds for the size of a minimal vertex-separating path system for trees, which we show to be tight in many cases. We obtain similar results for a variation of the definition, where we require the path system to separate edges and vertices simultaneously. Finally, we investigate the size of a minimal vertex-separating path system in Erd\H{o}s--R\'enyi random graphs. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
