Pelto, Mikko - Maximum difference about the size of optimal identifying codes in graphs differing by one vertex

dmtcs:2107 - Discrete Mathematics & Theoretical Computer Science, May 6, 2015, Vol. 17 no. 1 (in progress)
Maximum difference about the size of optimal identifying codes in graphs differing by one vertex

Authors: Pelto, Mikko

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.


Source : oai:HAL:hal-01196851v1
Volume: Vol. 17 no. 1 (in progress)
Section: Graph Theory
Published on: May 6, 2015
Submitted on: June 25, 2013
Keywords: identifying codes,graph theory,twin-free graphs,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]


Share

Browsing statistics

This page has been seen 17 times.
This article's PDF has been downloaded 28 times.