Discrete Mathematics & Theoretical Computer Science, Vol 16, No 1 (2014)

Font Size:  Small  Medium  Large

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

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


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