Edge identifying codes

We study the edge identifying code problem, i.e. the identifying code problem in line graphs. If γID(G) denotes the size of a minimum identifying code of a graph G, we show that the usual bound γID(G)⩾⌈log2(n+1)⌉, where n denotes the order of G, can be improved to Θ(n) in the class of line graphs. Moreover this bound is tight. We also prove that the upper bound γID(L(G))⩽2⋅|V(G)|−4 holds. This implies that a conjecture of R. Klasing, A. Kosowski, A. Raspaud and the first author holds for a subclass of line graphs. Finally, we show that the edge identifying code problem is NP-complete, even for the class of planar bipartite graphs of maximum degree 3 and arbitrarily large girth.