Victor Falgas-Ravry: Separating path systems

Let G be a graph on n vertices. A family F of paths in G constitutes a separating system of G if for ever pair of distinct edges e,f in E(G) there exists a path p in F which contains exactly one of e and f. How small a separating path system can we find?

This question arises naturally in the context of network design. The graph G represents a communication network in which one link is defective; to identify this link, we can send messages between nodes along predetermined paths. If a message does not reach its destination, then we deduce that the defective link lies on the corresponding path. A minimal separating path system thus allows us to determine precisely which link is defective using a minimal number of messages.

We show that for asymptotically almost all n-vertex graphs, we can find a separating system containing at most 48 n paths. In addition we prove some exact extremal results in the case where G is a tree.

This is joint work with Teeradej Kittipassorn, Daniel Korandi, Shoham Letzter and Bhargav Narayanan. Similar results have recently and independently been obtained by Balogh, Csaba, Martin and Pluhar.