The location-domination conjecture for twin-free graphs

Let GG be a graph on nn vertices. A twin-free graph is one with no two distinct vertices having the same open neighborhood, and LD(G)LD(G) denotes its location-domination number.

Location-domination conjecture. If GG is a twin-free graph on nn vertices, then

LD(G)n2.LD(G)\leq \frac{n}{2}.

This conjecture, due to Garijo, González and Márquez, concerns the size of a smallest locating-dominating set in a twin-free graph. The source proves the weaker bound LD(G)58nLD(G)\leq \lceil\frac{5}{8}n\rceil, improving the earlier bound 23n\lfloor\frac{2}{3}n\rfloor, so the conjectured bound remains open in the supplied source.

Sources & referencesView supporting material

Primary source

Nicolas Bousquet, Quentin Chuet, Victor Falgas-Ravry, Amaury Jacques and Laure Morelle, “A note on locating-dominating sets in twin-free graphs”, arXiv:2405.18162 (2024).

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.