2022/09/09 by Belinda Wickes, Wickes, Belinda
Computer Science · Mathematics · #05C35 (Primary) 05C38 (Secondary) #Advanced Graph Theory Research #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2209.04302
openalex publication_date 2022/09/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Kn, denoted f(Kn). Our first main result is a construction that shows f(Kn) ≤ ((21)/(16)+o(1))n for sufficiently large n. We also show that f(Kn) ≤ n whenever n=p,p+1 for prime p. It is known by simple argument that f(Kn) ≥ n-1 for all 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 Kn. Hence existence of a generator path for some Kn gives f(Kn) ≤ n. We construct such paths for all Kn with n ≤ 20, and show that generator paths exist whenever n is prime.