Graphs where every k-subset of vertices is an identifying set
: Sylvain Gravier, Svante Janson, Tero Laihonen, Sanna Maarit Ranto
Publisher: DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE
: 2014
: Discrete Mathematics and Theoretical Computer Science
: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE
: DISCRETE MATH THEOR
: 16
: 1
: 73
: 88
: 16
: 1462-7264
: http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1496/4385
Let G = ( V, E) be an undirected graph without loops and multiple edges. A subset C subset of V is called identifying if for every vertex x is an element of 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 l vertices is considered as well.