The half-order conjecture for locating-dominating sets in twin-free graphs
The half-order conjecture for locating-dominating sets in twin-free graphs
Let be a finite graph. A set is a locating-dominating set if it dominates every vertex outside and, for every two distinct vertices , the sets and are distinct. Write for the minimum cardinality of a locating-dominating set, and let be the order of . 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 of order without isolated vertices satisfies
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.