Name
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. |
Year | Venue | Keywords |
|---|---|---|
2014 | DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE | identifying code,extremal graph,strongly regular graph,Plotkin bound |
Field | DocType | Volume |
Graph theory,Integer,Discrete mathematics,Combinatorics,Vertex (geometry),Level structure,Cycle graph,Independent set,Multiple edges,Mathematics,Computational complexity theory | Journal | 16.0 |
Issue | ISSN | Citations |
1.0 | 1462-7264 | 4 |
PageRank | References | Authors |
0.49 | 16 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sylvain Gravier | 1 | 486 | 59.01 |
| Svante Janson | 2 | 1009 | 149.67 |
| Tero Laihonen | 3 | 363 | 39.39 |
| Sanna Maarit Ranto | 4 | 4 | 0.49 |