Locating-dominating sets in twin-free graphs

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)\cap D\ne N(v)\cap 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 ${\gamma }_L(G)$, is the minimum cardinality of a locating-dominating set in $G$. It is conjectured [D. Garijo, A. González and A. Márquez. The difference between the metric dimension and the determining number of a graph. Applied Mathematics and Computation 249 (2014), 487--501] that if $G$ is a twin-free graph of order $n$ without isolated vertices, then ${\gamma }_L(G)\le \frac{n}{2}$. We prove the general bound ${\gamma }_L(G)\le \frac{2n}{3}$, slightly improving over the $\lfloor \frac{2n}{3}\rfloor +1$ bound of Garijo et al. We then provide constructions of graphs reaching the $\frac{n}{2}$ 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.

11 pages; 4 figures

References in corpus (2)

• Extremal graphs for the identifying code problem
• Resolving sets for breaking symmetries of graphs

Cited by in corpus (8)

• Location-domination and matching in cubic graphs
• Location-domination in line graphs
• Characterizing extremal graphs for open neighbourhood location-domination
• Domination and location in twin-free digraphs
• Revisiting and improving upper bounds for identifying codes
• Bounds and extremal graphs for total dominating identifying codes
• Locating-dominating partitions for some classes of graphs
• Progress towards the two-thirds conjecture on locating-total dominating sets