Exact upper bounds for the minimum sizes of strong and weak separating path systems of cliques

Abstract

We prove an upper bound of $n+9$ for the strong separation number of the complete graph $K_n$, and an upper bound of $n+1$ for its weak separation number. This improves on the previous best known bound of $(1+o(1))n$ for both cases.

arXiv comment19 pages, improved exposition incorporating comments from reviewers