DGGH's characterization conjecture for cop-win oriented graphs

At least 7 years old · documented by

An oriented graph DD 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 DD is cop-win if and only if DD contains exactly one vertex of in-degree 00, every vertex is reachable from that vertex, and every directed cycle of DD is cop-dominated.

The conjecture is attributed in the source to DGGH16. No resolution evidence is supplied in the paper excerpt.

References

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).

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.