A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

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




TekijätSylvain Gravier, Svante Janson, Tero Laihonen, Sanna Maarit Ranto

KustantajaDISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE

Julkaisuvuosi2014

JournalDiscrete Mathematics and Theoretical Computer Science

Tietokannassa oleva lehden nimiDISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE

Lehden akronyymiDISCRETE MATH THEOR

Vuosikerta16

Numero1

Aloitussivu73

Lopetussivu88

Sivujen määrä16

ISSN1462-7264

Verkko-osoitehttp://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1496/4385


Tiivistelmä

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