### Graphs where every k-subset of vertices is an identifying set

*Sylvain Gravier, Svante Janson, Tero Laihonen, Sanna Maarit Ranto*

#### Abstract

Let G=(V,E) be an undirected graph without loops and
multiple edges. A subset C⊆V is called

*identifying*if for every vertex x∈V the intersection of C and the closed neighbourhood of x is nonempty, and these intersections are different for different vertices x. Let k be a positive integer. We will consider graphs where*every*k-subset is identifying. We prove that for every k>1 the maximal order of such a graph is at most 2k-2. Constructions attaining the maximal order are given for infinitely many values of k. The corresponding problem of k-subsets identifying any at most ℓ vertices is considered as well.Full Text: PDF