Title: Separating path systems in trees Show Chinese title

Title: 树中的分离路径系统

Abstract: 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. Show Chinese abstract

Abstract: 对于一个图$G$，边分离（或顶点分离）路径系统$G$是$G$中的一族路径，使得对于任何一对边$e_1, e_2$（或顶点） 顶点对$v_1, v_2$) 的$G$中，至少有一个路径在该族中包含$e_1$和$e_2$之一（分别地，$v_1$和$v_2$）但不包含另一个。 我们确定了任意树$T$的最小边分离路径系统的大小，作为其叶子数和度为二的顶点数的函数。 我们得到了树的最小顶点分离路径系统的大小的界限，并且我们证明在许多情况下这些界限是紧的。 我们得到了一种定义变体的类似结果，其中要求路径系统同时分离边和顶点。 最后，我们研究了 Erdős--Rényi 随机图中最小顶点分离路径系统的大小。