A1 Refereed original research article in a scientific journal
Optimal identification of sets of edges using 2-factors
Authors: Junnila V, Laihonen T
Publisher: ELSEVIER SCIENCE BV
Publication year: 2013
Journal: Discrete Mathematics
Journal name in source: DISCRETE MATHEMATICS
Journal acronym: DISCRETE MATH
Number in series: 16
Volume: 313
Issue: 16
First page : 1636
Last page: 1647
Number of pages: 12
ISSN: 0012-365X
DOI: https://doi.org/10.1016/j.disc.2013.04.015
Abstract
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.
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.
UTU Research Portal