Location-domination in line graphs

A set DD of vertices of a graph GG is locating if every two distinct vertices outside DD have distinct neighbors in DD; that is, for distinct vertices uu and vv outside DD, N(u)∩D≠N(v)∩DN(u)∩D≠N(v)∩D, where N(u)N(u) denotes the open neighborhood of uu. If DD is also a dominating set (total dominating set), it is called a locating-dominating set (respectively, locating-total dominating set) of GG. A graph GG is twin-free if every two distinct vertices of GG have distinct open and closed neighborhoods. It is conjectured (Garijo et al., 2014 [15]) and (Foucaud and Henning, 2016 [12]) respectively, that any twin-free graph GG without isolated vertices has a locating-dominating set of size at most one-half its order and a locating-total dominating set of size at most two-thirds its order. In this paper, we prove these two conjectures for the class of line graphs. Both bounds are tight for this class, in the sense that there are infinitely many connected line graphs for which equality holds in the bounds.