Directed Path-width and Monotonicity in Digraph Searching

Directed path-width was defined by Reed, Thomas and Seymour around 1995. The author and P. Hajnal defined a cops-and-robber game on digraphs in 2000. We prove that the two notions are closely related and for any digraph D, the corresponding graph parameters differ by at most one. The result is achie...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2006-06, Vol.22 (2), p.161-172
Main Author: Barát, János
Format: Article
Language:English
Subjects:
Game theory
Graph theory
Mathematics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Directed path-width was defined by Reed, Thomas and Seymour around 1995. The author and P. Hajnal defined a cops-and-robber game on digraphs in 2000. We prove that the two notions are closely related and for any digraph D, the corresponding graph parameters differ by at most one. The result is achieved using the mixed-search technique developed by Bienstock and Seymour. A search is called monotone, in which the robber's territory never increases. We show that there is a mixed-search of D with k cops if and only if there is a monotone mixed-search with k cops. For our cops-and-robber game we get a slightly weaker result: the monotonicity can be guaranteed by using at most one extra cop. [PUBLICATION ABSTRACT]
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-005-0627-y