The two-thirds conjecture for locating-total dominating sets
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.