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

Lehti:Discrete 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