A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Graphs where every k-subset of vertices is an identifying set
Tekijät: Sylvain Gravier, Svante Janson, Tero Laihonen, Sanna Maarit Ranto
Kustantaja: DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE
Julkaisuvuosi: 2014
Journal: Discrete Mathematics and Theoretical Computer Science
Tietokannassa oleva lehden nimi: DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: DISCRETE MATH THEOR
Vuosikerta: 16
Numero: 1
Aloitussivu: 73
Lopetussivu: 88
Sivujen määrä: 16
ISSN: 1462-7264
Verkko-osoite: 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.