Discriminating Codes in (Bipartite) Planar Graphs
European Journal of Combinatorics, Vol. 29, pp. 1353-1364, 2008.
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 a connected undirected bipartite graph G=(V=I $\cup$ A,E), with no edges 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 classes of bipartite graphs, namely trees and, more generally, (bipartite) planar graphs.