Discriminating Codes in Bipartite Graphs: Bounds, Extremal Cardinalities, Complexity
Advances in Mathematics of Communications, Vol. 2(4), pp. 403-420, 2008.
Emmanuel CHARBIT, Irène CHARON, Gérard COHEN, Olivier HUDRY & Antoine LOBSTEIN
Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
{charon, cohen, hudry, lobstein}@enst.fr
Abstract. 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 included in 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.