Graphs where every k-subset of vertices is an identifying set
2014 (English)In: DISCRETE MATH THEOR, ISSN 1462-7264, Vol. 16, no 1, 73-88 p.Article in journal (Refereed) Published
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.
Place, publisher, year, edition, pages
2014. Vol. 16, no 1, 73-88 p.
identifying code, extremal graph, strongly regular graph, Plotkin bound
IdentifiersURN: urn:nbn:se:uu:diva-235653ISI: 000342623000005OAI: oai:DiVA.org:uu-235653DiVA: diva2:761625