DISCRIMINATING CODES IN BIPARTITE GRAPHS: BOUNDS, EXTREMAL CARDINALITIES, COMPLEXITY

被引:20
作者
Charbit, Emmanuel [1 ]
Charon, Irene [1 ,2 ]
Cohen, Gerard [1 ,2 ]
Hudry, Olivier [1 ,2 ]
Lobstein, Antoine [1 ,2 ]
机构
[1] TELECOM ParisTech, Inst TELECOM, F-75634 Paris 13, France
[2] CNRS, LTCI, UMR 5141, F-75634 Paris 13, France
关键词
Graph theory; bipartite graphs; discriminating codes; identifying codes; locating-dominating codes; separating codes; complexity;
D O I
10.3934/amc.2008.2.403
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Consider an undirected bipartite graph G = (V = I boolean OR A, E), with no edge inside I nor A. For any vertex v is an element of V, let N(v) be the set of neighbours of v. A code C subset of A is said to be discriminating if all the sets N(i) boolean AND C, i is an element of 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.
引用
收藏
页码:403 / 420
页数:18
相关论文
共 36 条