Locating-dominating sets in twin-free graphs
Florent Foucaud
Universit\'e Blaise Pascal, Clermont-Ferrand (France)
Michael Henning
University of Johannesburg (South Africa)
Christian L\"{o}wenstein
Universit\"at Ulm (Germany)
Thomas Sasse
Universit\"at Ulm (Germany)
PDF
Minisymposium: METRIC DIMENSION AND RELATED PARAMETERS
Content: A locating-dominating set of a graph is a dominating set such that each vertex not in the set has a unique neighbourhood within the set. In 2014, Garijo, Gonz\'alez and M\'arquez conjectured that any twin-free graph without isolated vertices admits a locating-dominating set of size at most half the order. We discuss this beautiful conjecture and present proofs of it for the special cases of split graphs, cobipartite graphs, cubic graphs, and line graphs. We also discuss the set of graphs having location-domination number exactly half the order.