Skip to Main content Skip to Navigation
Journal articles

Maximum difference about the size of optimal identifying codes in graphs differing by one vertex

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.
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-01196851
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, September 10, 2015 - 3:17:11 PM
Last modification on : Thursday, September 7, 2017 - 1:03:43 AM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:09:19 AM

File

dmtcs-17-1-22.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Mikko Pelto. Maximum difference about the size of optimal identifying codes in graphs differing by one vertex. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (1), pp.339--356. ⟨10.46298/dmtcs.2107⟩. ⟨hal-01196851⟩

Share

Metrics

Record views

38

Files downloads

486