返回
Separating path systems in trees
DOI:10.1007/s10957-025-02894-z.png)
摘要
En 中文
对于图G,G的边分离(resp. 顶点分离)路径系统是一个路径族,使得对于G中的任意一对边e1,e2(resp. 任意一对顶点v1,v2),族中至少存在一条路径包含e1或e2(resp. v1或v2)但不同时包含两者。我们确定了任意树T的最小边分离路径系统的大小,将其表示为其叶节点数和度为二的顶点数的函数。我们得到了树的最小顶点分离路径系统大小的界,并证明在许多情况下这些界是紧的。对于定义的一种变体,即要求路径系统同时分离边和顶点,我们也得到了类似的结果。最后,我们研究了Erdős-Rényi随机图中最小顶点分离路径系统的大小。
Keyword:
Separating path systems
Separating families
Identifying families
Trees
期刊
J
IF:
1.5
论文数:
184
被引数:
8.2K

