The half-order conjecture for locating-dominating sets in twin-free graphs

Let GG be a finite graph. A set CV(G)C\subseteq V(G) is a locating-dominating set if it dominates every vertex outside CC and, for every two distinct vertices u,vV(G)Cu,v\in V(G)\setminus C, the sets N(u)CN(u)\cap C and N(v)CN(v)\cap C are distinct. Write γLD(G)\gamma^{LD}(G) for the minimum cardinality of a locating-dominating set, and let n=V(G)n=|V(G)| be the order of GG. A graph is twin-free if it has neither two vertices with equal open neighborhoods nor two vertices with equal closed neighborhoods; an isolated vertex has degree zero. The half-order conjecture. Every twin-free graph GG of order nn without isolated vertices satisfies

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

This conjecture, originally proposed in the cited work and subsequently studied in the cited formulation, asserts a sharp universal upper bound for locating-dominating sets in twin-free graphs. Its resolution is not specified in the supplied source material.

Sources & referencesView supporting material

Primary source

Dipayan Chakraborty, Anni Hakanen and Tuomo Lehtilä, “The n/2-bound for locating-dominating sets in subcubic graphs”, arXiv:2406.19278 (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.