ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be a graph of order nn. A set D⊆V(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.

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.