Belinda Wickes

Separating Path Systems for the Complete Graph

For any graph G, a separating path system of G is a family of paths in G with the property that for any edges e and e' there is at least one path that contains one of e and e' but not the other. A natural problem is to determine the size of the smallest separating path system for a given G, denoted f(G).

In this talk we focus on determining f(K_n). It is known that n-1 ≤ f(K_n) ≤ 2n+4. We will use a concept we call generator paths which reduces the problem to that of finding a single path with particular properties. We then use these generator paths to construct separating path families for K_n improving the upper bound to f(K_n) ≤ (21/16 + o(1))n in general, and f(K_n) ≤ n in the case where n=p,p+1 for prime p.