New Bounds for Codes Identifying Vertices in Graphs
New Bounds for Codes Identifying Vertices in Graphs
复制标题
DOI：
10.37236/1451
复制
发表时间：
1999-03
期刊：
影响因子：
--
通讯作者：
G. Cohen;I. Honkala;A. Lobstein;G. Zémor
中科院分区：
文献类型：
--
作者：
G. Cohen;I. Honkala;A. Lobstein;G. Zémor
设G=（V，E）$是一个无向图.设$C$是顶点的子集，我们称之为代码。对于V$中的任何顶点$v\，相邻集$N（v，C）$是$C$中距离$v$至多为1的顶点的集合。我们说代码$C$标识$G$的顶点，如果相邻集合$N（v，C），v\in V，$都是非空且不同的。识别码$C$的最小尺寸是多少？我们专注于的情况下，当$G$是二维正方形格，并改善以前的上限和下限的最小尺寸这样的代码。
Let $G=(V,E)$ be an undirected graph. Let $C$ be a subset of vertices that we shall call a code. For any vertex $v\in V$, the neighbouring set $N(v,C)$ is the set of vertices of $C$ at distance at most one from $v$. We say that the code $C$ identifies the vertices of $G$ if the neighbouring sets $N(v,C), v\in V,$ are all nonempty and different. What is the smallest size of an identifying code $C$ ? We focus on the case when $G$ is the two-dimensional square lattice and improve previous upper and lower bounds on the minimum size of such a code.