Information Processing Letters, Vol. 115, pp. 699-702, 2015.
Iiro HONKALA (#), Olivier HUDRY (*) & Antoine LOBSTEIN (*)
(#) Department of Mathematics and Statistics
University of Turku, 20014 Turku, Finland
honkala@utu.fi
(*) Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
{olivier.hudry, antoine.lobstein}@telecom-paristech.fr
Résumé. Let G be a simple, undirected graph with vertex set V. For every v in V, we denote by N(v) the set of neighbours of v, and let N[v] = N(v) $\cup$ {v}. A subset C of V is said to be a dominating code in G if the sets N[v] $\cap$ C, v in V, are all nonempty. A subset C of V is said to be a locating-dominating code in G if the sets N[v] $\cap$ C, v in V\C, are all nonempty and distinct. The smallest size of a dominating (resp., locating-dominating) code in G is denoted by d(G) (resp., c(G)).
We study the ensemble of all the different optimal dominating (resp., locating-dominating) codes C, i.e., such that |C|=d(G) (resp., |C|=c(G)) in a graph G, and strongly link this problem to that of induced subgraphs of Johnson graphs.