论文标题
分开完整图的路径系统
Separating Path Systems for the Complete Graph
论文作者
论文摘要
对于任何图$ g $，$ g $的分离路径系统是$ g $的一家属性的属性，对于$ e（g）$中的任何一对边缘，家庭中至少有一个路径，其中包含一个边缘，而不是另一个边缘。我们研究了$ k_n $的最小分离路径系统的大小，表示为$ f（k_n）$。 我们的第一个主要结果是一个构造，显示$ f（k_n）\ leq \ left（\ frac {21} {16} {16}+o（1）\ right）n $，用于足够大的$ n $。我们还表明，每当$ n = p，p+1 $ for Prime $ p $时，$ f（k_n）\ leq n $。通过简单的参数知道$ f（k_n）\ geq n-1 $ in \ mathbb {n} $中的所有$ n \。 我们构造中的一个关键想法是减少问题，以找到具有某些特定属性的单个路径，我们称为发电机路径。这些定义的方式使生成器路径的$ N $环状旋转为$ k_n $提供了一个分离的路径系统。因此，存在一些$ k_n $的生成器路径给出$ f（k_n）\ leq n $。我们使用$ n \ leq 20 $为所有$ k_n $构建此类路径，并证明每当$ n $是Prime时，生成器路径就存在。
For any graph $G$, a separating path system of $G$ is a family of paths in $G$ with the property that for any pair of edges in $E(G)$ there is at least one path in the family that contains one edge but not the other. We investigate the size of the smallest separating path system for $K_n$, denoted $f(K_n)$. Our first main result is a construction that shows $f(K_n) \leq \left(\frac{21}{16}+o(1)\right)n$ for sufficiently large $n$. We also show that $f(K_n) \leq n$ whenever $n=p,p+1$ for prime $p$. It is known by simple argument that $f(K_n) \geq n-1$ for all $n \in \mathbb{N}$. A key idea in our construction is to reduce the problem to finding a single path with some particular properties we call a Generator Path. These are defined in such a way that the $n$ cyclic rotations of a generator path provide a separating path system for $K_n$. Hence existence of a generator path for some $K_n$ gives $f(K_n) \leq n$. We construct such paths for all $K_n$ with $n \leq 20$, and show that generator paths exist whenever $n$ is prime.
