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

JournalDiscrete 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