The two-thirds conjecture for locating-total dominating sets
The two-thirds conjecture for locating-total dominating sets
Let be a graph of order . A set is a locating-total dominating set if every vertex has a neighbor in , and any two vertices outside have distinct neighborhoods within . Write for the minimum size of such a set. A graph is twin-free if it contains no pair of twins, where twins have either the same open neighborhood or the same closed neighborhood; it is isolate-free if it has no isolated vertex.
Two-thirds conjecture. Every twin-free isolate-free graph of order satisfies
The conjecture asks for a universal upper bound on locating-total domination in the absence of twins. It was proved for graphs with no -cycle, for line graphs, and for graphs of sufficiently large minimum degree under a related conjecture; a stronger bound with factor is known for claw-free cubic graphs. The general case remains open.
Sources & referencesView supporting material
Primary source
Dipayan Chakraborty, Florent Foucaud, Anni Hakanen, Michael A. Henning and Annegret K. Wagler, “Progress towards the two-thirds conjecture on locating-total dominating sets”, arXiv:2211.14178 (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.