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