Graphs where every k-subset of vertices is an identifying set
| dc.creator | Gravier, Sylvain | |
| dc.creator | Janson, Svante | |
| dc.creator | Laihonen, Tero | |
| dc.creator | Ranto, Sanna | |
| dc.date | 2009-02-03 | |
| dc.date.accessioned | 2026-07-07T12:37:16Z | |
| dc.date.available | 2026-07-07T12:37:16Z | |
| dc.description | Let $G=(V,E)$ be an undirected graph without loops and multiple edges. A subset $C\subseteq V$ is called \emph{identifying} if for every vertex $x\in 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 \emph{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 $\ell$ vertices is considered as well. | |
| dc.description | 21 pages | |
| dc.identifier | https://arxiv.org/abs/0902.0443 | |
| dc.identifier | http://arxiv.org/abs/0902.0443 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/218381 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C69, 94C12, 05C70, 05C75 | |
| dc.title | Graphs where every k-subset of vertices is an identifying set | |
| dc.type | text |