Geodesics in graphs, an extremal set problem, anti perfect hash families

A set U of vertices of a graph G is called it geodetic set if the Union of all the geodesics joining pairs of points of U is the whole graph G. One result in this paper is a tight lower bound oil tile minimum number of vertices in a geodetic set. In order to obtain that result, the following extremal set problem is solved. Find tile minimum cardinality of a collection subsets of [n] = {1, 2,..., n} such that, for any two distinct elements x,y is an element of [n], there exists disjoint subsets A(x), A(y) is an element of S such that x is an element of A(x) and y is an element of A(y). This separating set problem can be generalized, and some bounds can be obtained from known results on families of hash functions.