ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be a connected graph, and let lcapt⁡(G)\operatorname{lcapt}(G) denote its localization capture time, namely the minimum number of rounds needed for the minimum number ζ(G)\zeta(G) of cops to locate an omniscient robber on GG. A family of graphs is well-localizable if there exists a constant DD such that every graph GG in the family satisfies

lcapt⁡(G)≤D∣V(G)∣.\operatorname{lcapt}(G)\leq D|V(G)|.

Localization Capture Time Conjecture (LCTC). The family of all connected graphs is well-localizable; equivalently, there exists a constant DD such that every connected graph GG satisfies

lcapt⁡(G)≤D∣V(G)∣.\operatorname{lcapt}(G)\leq D|V(G)|.

This conjecture seeks a linear upper bound on localization capture time in terms of the number of vertices. Exact bounds are known for several graph families, including trees and outerplanar graphs, but the general connected-graph 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.