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