The two-thirds conjecture for locating-total dominating sets

Let GG be a graph of order nn. A set DV(G)D\subseteq V(G) is a locating-total dominating set if every vertex has a neighbor in DD, and any two vertices outside DD have distinct neighborhoods within DD. Write γtL(G)\gamma_t^L(G) 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 GG of order nn satisfies

γtL(G)2n3.\gamma_t^L(G)\leq\frac{2n}{3}.

The conjecture asks for a universal upper bound on locating-total domination in the absence of twins. It was proved for graphs with no 44-cycle, for line graphs, and for graphs of sufficiently large minimum degree under a related conjecture; a stronger bound with factor 12\frac{1}{2} 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

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.