Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity
Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity
复制标题
二分图中的判别代码：界限、极值基数、复杂性
DOI：
10.3934/amc.2008.2.403
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
A. Lobstein
中科院分区：
文献类型：
--
作者：
Emmanuel Charbit;I. Charon;G. Cohen;O. Hudry;A. Lobstein
考虑一个无向二部图$G=（V=I\cup A，E）$，其中I$和A$内没有边。对于V$中的任何顶点$v\，令$N（v）$是$v$的邻居集。如果所有的集合$N（i）\cap C$，$i \in I$，都是非空且不同的，则称代码$C \subseteq A$是有区别的。研究了判别码的一些性质。特别是，我们给这些代码的最小尺寸上的界限，调查图的最小判别码的大小接近上限，或在特定的图形给出确切的最小尺寸，我们还给出了一个NP-完全性的结果。
Consider an undirected bipartite graph $G=(V=I\cup A,E)$, with no edge inside $I$ nor $A$. For any vertex $v\in V$, let $N(v)$ be the set of neighbours of $v$. A code $C \subseteq A$ is said to be discriminating if all the sets $N(i) \cap C$, $i \in I$, are nonempty and distinct. We study some properties of discriminating codes. In particular, we give bounds on the minimum size of these codes, investigate graphs where minimal discriminating codes have size close to the upper bound, or give the exact minimum size in particular graphs; we also give an NP-completeness result.