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.

Back to all abstracts