DGGH's characterization conjecture for cop-win oriented graphs
DGGH's characterization conjecture for cop-win oriented graphs
An oriented graph is a directed graph obtained by orienting the edges of a simple undirected graph; a directed cycle is cop-dominated if the robber cannot avoid capture by entering it along some path and then repeatedly traveling around the cycle. DGGH's conjecture. An oriented graph is cop-win if and only if contains exactly one vertex of in-degree , every vertex is reachable from that vertex, and every directed cycle of is cop-dominated.
The conjecture is attributed in the source to DGGH16. No resolution evidence is supplied in the paper excerpt.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Devvrit Khatri, Natasha Komarov, Aaron Krim-Yee, Nithish Kumar, Ben Seamone, Virgélot Virgile and AnQi Xu, “A study of cops and robbers in oriented graphs”, arXiv:1811.06155 (2019).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.