Skip to main content
SpringerLink
Log in

Directed Path-width and Monotonicity in Digraph Searching

  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Adler, I.: A note on monotonicity in digraph searching. Manuscript, 2003

  2. Barát, J.: Width-type graph parameters (PhD-Thesis). University of Szeged, Hungary, 2001

  3. Bienstock, D., Seymour, P.: Monotonicity in Graph Searching. J. Algo. 12, 239–245 (1991)

    Google Scholar 

  4. Bienstock, D., Robertson, N., Seymour, P., Thomas, R.: Quickly Excluding a Forest. J. Combin. Theory Ser. B 52, 274–283 (1991)

    Google Scholar 

  5. Dendris, N.D., Kirousis, L.M., Thilikos, D.M.: Fugitive-search games on graphs and related parameters. Theoret. Comput. Sci. 172, 233–254 (1997)

    Google Scholar 

  6. Diestel, R.: Graph Theory. Springer, 1997; xiv+289 pp. and second edition (Springer 2000) xiv+313 pp.

  7. Fomin, F.V., Thilikos, D.M.: On the monotonicity of games generated by symmetric submodular functions. Discrete Appl. Math. 131, 323–335 (2003)

    Google Scholar 

  8. Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Directed Tree-Width. J. Combin. Theory Ser. B 82, 138–154 (2001)

    Google Scholar 

  9. Reed, B.: Introducing Directed Tree Width, 6th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1999), 8 pp. (electronic), Electron. Notes Discrete Math. 3, Elsevier, Amsterdam, 1999

  10. Thomas, R.: Tree-decomposition of graphs. Class notes, 1996, http://www.math. gatech.edu/~thomas/tree.ps

  11. Thomas, R.: Personal communication

  12. Thomassen, C.: Even Cycles in Directed Graphs. Europ. J. Combinatorics 6, 85–89 (1985)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Technical University of Denmark, B.303. 2800, Lyngby, Denmark

    János Barát

Authors
  1. János Barát
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to János Barát.

Additional information

On leave from Bolyai Institute, University of Szeged, Hungary. This research has been supported by a Marie Curie Fellowship of the European Community under contract number HPMF-CT-2002-01868 and by OTKA Grants F.030737 and T.34475.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Barát, J. Directed Path-width and Monotonicity in Digraph Searching. Graphs and Combinatorics 22, 161–172 (2006). https://doi.org/10.1007/s00373-005-0627-y

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-005-0627-y

Keywords

Search

Navigation