Name
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.disc.2013.04.015 | Discrete Mathematics |
Keywords | Field | DocType |
Edge identification,Identifying code,Factor of a graph,Sets of edges | Strength of a graph,Discrete mathematics,Combinatorics,Line graph,Edge cover,Bipartite graph,Edge contraction,Independent set,Mathematics,Planar graph,Complement graph | Journal |
Volume | Issue | ISSN |
313 | 16 | 0012-365X |
Citations | PageRank | References |
1 | 0.37 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ville Junnila | 1 | 43 | 10.51 |
| Tero Laihonen | 2 | 363 | 39.39 |