uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Graphs where every k-subset of vertices is an identifying set
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
2014 (English)In: DISCRETE MATH THEOR, ISSN 1462-7264, Vol. 16, no 1, 73-88 p.Article in journal (Refereed) Published
Abstract [en]

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.
Keyword [en]
identifying code, extremal graph, strongly regular graph, Plotkin bound
National Category
URN: urn:nbn:se:uu:diva-235653ISI: 000342623000005OAI: oai:DiVA.org:uu-235653DiVA: diva2:761625
Available from: 2014-11-07 Created: 2014-11-06 Last updated: 2014-11-07Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Janson, Svante
By organisation
Department of Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 140 hits
ReferencesLink to record
Permanent link

Direct link