Maximum difference about the size of optimal identifying codes in graphs differing by one vertex
Mikko Pelto
Abstract
Let G=(V,E) be a simple undirected graph. We call any
subset C⊆V an identifying code if the sets
I(v)={c∈C | {v,c}∈E or
v=c } are distinct and non-empty for all
vertices v∈V. A graph is called twin-free if there
is an identifying code in the graph. The identifying code with minimum
size in a twin-free graph G is called the optimal
identifying code and the size of such a code is denoted by
γ(G). Let GS denote the
induced subgraph of G where the vertex set
S⊂V is deleted. We provide a tight upper bound for
γ(GS)-γ(G) when both graphs are
twin-free and |V| is large enough with respect to
|S|. Moreover, we prove tight upper bound when
G is a bipartite graph and |S|=1.
Full Text: PDF PostScript