A1 Refereed original research article in a scientific journal

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




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

PublisherDISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE

Publication year2014

Journal:Discrete Mathematics and Theoretical Computer Science

Journal name in sourceDISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE

Journal acronymDISCRETE MATH THEOR

Volume16

Issue1

First page 73

Last page88

Number of pages16

ISSN1462-7264

Web address http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1496/4385


Abstract

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