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

About 12 years old · traced to

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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.