Optimal identification of sets of edges using 2-factors

: Junnila V, Laihonen T

Publisher: ELSEVIER SCIENCE BV

: 2013

: Discrete Mathematics

: DISCRETE MATHEMATICS

: DISCRETE MATH

: 16

: 313

: 16

: 1636

: 1647

: 12

: 0012-365X

DOI: https://doi.org/10.1016/j.disc.2013.04.015

The problem of identifying a single arbitrary edge in a graph using edge-identifying codes was recently considered by Foucaud et al. (in press) [4]. In this paper, we focus on locating more than one edge. First, we classify the graphs in which this is possible. Furthermore, for such graphs, we give a simple characterization of edge-identifying codes. Using the characterization, we give various lower and upper bounds for edge-identifying codes in terms of the order and size of a graph. In particular, codes with the minimum cardinality are obtained with the aid of 2-factors. In addition, we consider how the cardinality of the smallest edge-identifying codes behaves when an edge is added to a graph. (C) 2013 Elsevier B.V. All rights reserved.