New bounds for codes identifying vertices in graphs (Q1283874): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: Gérard D. Cohen / rank | |||
Property / author | |||
Property / author: Antoine C. Lobstein / rank | |||
Revision as of 11:01, 21 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New bounds for codes identifying vertices in graphs |
scientific article |
Statements
New bounds for codes identifying vertices in graphs (English)
0 references
31 March 1999
0 references
Suppose \(G\) is an undirected graph and \(C\) a subset of the vertices of \(G\) which is called a code. For any vertex \(v\) of \(G\), the neighboring set is the set of vertices in \(C\) at a distance at most 1 from \(v\). The code \(C\) is said to identify the vertices of \(G\) if the neighboring sets are all nonempty and different. The authors consider \(G\) a square grid drawn on a torus and establish the minimum density \(D\) of an identifying code of the limiting infinite graph as \(23/66\leq D\leq 5/14\).
0 references
code
0 references
infinite graph
0 references