DISCRIMINATING CODES IN BIPARTITE GRAPHS: BOUNDS, EXTREMAL CARDINALITIES, COMPLEXITY
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.
discriminating codes bipartite graphs complexity graph theory identifying codes locating-dominating codes separating codes