Garijo et al.'s locating-dominating set conjecture for twin-free graphs

From papers

Let GG be a twin-free graph of order nn without isolated vertices. A locating-dominating set is a dominating set DD such that every two distinct vertices outside DD have distinct neighborhoods in DD; let γL(G)\gamma_L(G) denote the minimum cardinality of a locating-dominating set of GG.

Garijo et al.'s conjecture. Every twin-free graph GG of order nn without isolated vertices satisfies

γL(G)n2.\gamma_L(G)\leq \frac{n}{2}.

This conjecture proposes a universal upper bound on the locating-dominating number of twin-free graphs. The supplied source does not indicate whether the conjecture has been resolved.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Florent Foucaud, Michael A. Henning, Christian Löwenstein and Thomas Sasse, “Locating-dominating sets in twin-free graphs”, arXiv:1412.2376 (2015).

Solutions 0

No solutions have been posted yet.