Résumé
Consider a connected undirected graph G = (V,E), a subset of vertices C ⊆ V, and an integer r ≥ 1; for any vertex v ∈ V, let Br(v) denote the ball of radius r centered at v, i.e., the set of all vertices linked to v by a path of at most r edges. If for all vertices v ∈ V, the sets Br(v) {n-ary intersection} C are all nonempty and different, then we call C an r-identifying code. It is known that the cardinality of a minimum r-identifying code in any connected undirected graph G having a given number, n, of vertices lies in the interval [⌈log2(n +1)⌉, n - 1], and that the values ⌈log2(n +1)⌉ and n - 1 can be achieved. Here, we prove that any inbetween value can also be reached.
| langue originale | Anglais |
|---|---|
| Pages (de - à) | 177-195 |
| Nombre de pages | 19 |
| journal | Australasian Journal of Combinatorics |
| Volume | 32 |
| état | Publié - 1 déc. 2005 |
Empreinte digitale
Examiner les sujets de recherche de « Possible cardinalities for identifying codes in graphs ». Ensemble, ils forment une empreinte digitale unique.Contient cette citation
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver