## Abstract

A set D of vertices of a graph G is locating if every two distinct vertices outside D have distinct neighbors in D; that is, for distinct vertices u and v outside D, N(u)∩D≠N(v)∩D, where N(u) denotes the open neighborhood of u. If D is also a dominating set (total dominating set), it is called a locating-dominating set (respectively, locating-total dominating set) of G. A graph G is twin-free if every two distinct vertices of G 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 G 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.

Original language | English |
---|---|

Pages (from-to) | 3140-3153 |

Number of pages | 14 |

Journal | Discrete Mathematics |

Volume | 340 |

Issue number | 1 |

DOIs | |

Publication status | Published - 6 Jan 2017 |

## Keywords

- Dominating sets
- Line graphs
- Locating-dominating sets
- Locating-total dominating sets
- Total dominating sets

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics