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




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

PublisherDISCRETE 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.




Last updated on 2024-26-11 at 15:44