New bounds for codes identifying vertices in graphs (Q1283874): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Gérard D. Cohen / rank | |||
Property / author | |||
Property / author: Antoine C. Lobstein / rank | |||
Property / author | |||
Property / author: Gérard D. Cohen / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Antoine C. Lobstein / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 03:47, 5 March 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