On the number of optimal identifying codes in a twin-free graph

Let G be a simple, undirected graph with vertex set  V. For v∈V and r≥1, we denote by BG,r(v) the ball of radius  r and centre  v. A set C⊆V is said to be an r-identifying code in  G if the sets BG,r(v)∩C, v∈V, are all nonempty and distinct. A graph G which admits an r-identifying code is called r-t...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2015-01, Vol.180, p.111-119
Main Authors: Honkala, Iiro, Hudry, Olivier, Lobstein, Antoine
Format: Article
Language:English
Subjects:
Combinatorics
Computer Science
Discrete Mathematics
Graph theory
Identifiable graphs
Identifying codes
Mathematics
Twin-free graphs
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 v∈V and r≥1, we denote by BG,r(v) the ball of radius  r and centre  v. A set C⊆V is said to be an r-identifying code in  G if the sets BG,r(v)∩C, v∈V, are all nonempty and distinct. A graph G which admits an r-identifying code is called r-twin-free or r-identifiable, and in this case the smallest size of an r-identifying code in  G is denoted by  γrID(G). We study the number of different optimal r-identifying codes C, i.e., such that |C|=γrID(G), that a graph G can admit, and try to construct graphs having “many” such codes.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2014.08.020