On the ensemble of optimal dominating and locating-dominating codes in a graph

Let G be a simple, undirected graph with vertex set V. For every v∈V, we denote by N(v) the set of neighbours of v, and let N[v]=N(v)∪{v}. A set C⊆V is said to be a dominating code in G if the sets N[v]∩C, v∈V, are all nonempty. A set C⊆V is said to be a locating-dominating code in G if the sets N[v...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2015-09, Vol.115 (9), p.699-702
Main Authors: Honkala, Iiro, Hudry, Olivier, Lobstein, Antoine
Format: Article
Language:English
Subjects:
Codes
Combinatorial problems
Computer science
Domination
Graph theory
Johnson graphs
Locating-dominating codes
Mathematical problems
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let G be a simple, undirected graph with vertex set V. For every v∈V, we denote by N(v) the set of neighbours of v, and let N[v]=N(v)∪{v}. A set C⊆V is said to be a dominating code in G if the sets N[v]∩C, v∈V, are all nonempty. A set C⊆V is said to be a locating-dominating code in G if the sets N[v]∩C, v∈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., ℓ(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|=ℓ(G)) in a graph G, and strongly link this problem to that of induced subgraphs of Johnson graphs. •We study the set of all optimal locating-dominating codes in a given graph.•There is a strong link between such sets and induced subgraphs of Johnson graphs.•Instead of locating-dominating codes we also consider dominating codes.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2015.04.005