## Abstract

A locating-dominating set of a graph G is a dominating set D of G with the additional property that 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. A graph is twin-free if every two distinct vertices have distinct open and closed neighborhoods. The location-domination number of G, denoted γ_{L}(G), is the minimum cardinality of a locating-dominating set in G. It is conjectured by Garijo et al. (2014) that if G is a twin-free graph of order n without isolated vertices, then γ_{L}(G)≤n2. We prove the general bound γ_{L}(G)≤2n3, slightly improving over the ⌊2n3⌋+1 bound of Garijo et al. We then provide constructions of graphs reaching the n2 bound, showing that if the conjecture is true, the family of extremal graphs is a very rich one. Moreover, we characterize the trees G that are extremal for this bound. We finally prove the conjecture for split graphs and co-bipartite graphs.

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

Pages (from-to) | 52-58 |

Number of pages | 7 |

Journal | Discrete Applied Mathematics |

Volume | 200 |

DOIs | |

Publication status | Published - 19 Feb 2016 |

## Keywords

- Dominating sets
- Locating-dominating sets

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics