Locating–dominating sets in twin-free graphs

A locating–dominating set of a graph GG is a dominating set DD of GG with the additional property that 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. A graph is twin-free if every two distinct vertices have distinct open and closed neighborhoods. The location–domination number of GG, denoted γL(G)γL(G), is the minimum cardinality of a locating–dominating set in GG. It is conjectured by Garijo et al. (2014) that if GG is a twin-free graph of order nn 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 GG that are extremal for this bound. We finally prove the conjecture for split graphs and co-bipartite graphs.