IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i22p4367-d978460.html
   My bibliography  Save this article

A Note on Some Weaker Notions of Cop-Win and Robber-Win Graphs

Author

Listed:
  • Shravan Luckraz

    (School of Public Finance and Taxation, Zhejiang University of Finance and Economics, Hangzhou 310018, China
    These authors contributed equally to this work.)

  • Gafurjan Ibragimov

    (Department of Digital Economics and Agrotechnologies, University of Digital Economics and Agrotechnologies, Tashkent 100022, Uzbekistan
    These authors contributed equally to this work.)

  • Bruno Antonio Pansera

    (Department of Law, Economics and Human Sciences & Decisions Lab, University Mediterranea of Reggio Calabria, Via dell’Universitá 25, I-89124 Reggio Calabria, Italy
    These authors contributed equally to this work.)

Abstract

The game of pursuit and evasion, when played on graphs, is often referred to as the game of cops and robbers. This classical version of the game has been completely solved by Nowakowski and Winkler, who gave the exact class of graphs for which the pursuer can win the game (cop-win). When the graph does not satisfy the dismantlability property, Nowakowski and Winkler’s Theorem does not apply. In this paper, we give some weaker notions of cop-win and robber-win graphs. In particular, we fix the number of cops to be equal to one, and we ask whether there exist sets of initial conditions for which the graph can be cop-win or robber-win. We propose some open questions related to this initial condition problem with the goal of developing both structural characterizations and algorithms that are computable in polynomial time (P) and that can solve weakly cop-win and weakly- robber-win graphs.

Suggested Citation

  • Shravan Luckraz & Gafurjan Ibragimov & Bruno Antonio Pansera, 2022. "A Note on Some Weaker Notions of Cop-Win and Robber-Win Graphs," Mathematics, MDPI, vol. 10(22), pages 1-6, November.
    • Handle: RePEc:gam:jmathe:v:10:y:2022:i:22:p:4367-:d:978460
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/22/4367/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/10/22/4367/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Shravan Luckraz, 2019. "A Survey on the Relationship Between the Game of Cops and Robbers and Other Game Representations," Dynamic Games and Applications, Springer, vol. 9(2), pages 506-520, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Bruno Antonio Pansera & Massimiliano Ferrara & Luca Guerrini & Tiziana Ciano, 2023. "Preface to the Special Issue on “Differential Games and Its Applications”," Mathematics, MDPI, vol. 11(13), pages 1-4, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Athanasios Kehagias & Georgios Konstantinidis, 2021. "Some Game-Theoretic Remarks on Two-Player Generalized Cops and Robbers Games," Dynamic Games and Applications, Springer, vol. 11(4), pages 785-802, December.
    2. Hamid Beladi & Xiao Luo & Reza Oladi & Nicholas S. P. Tay, 2023. "On stability of economic networks," Theory and Decision, Springer, vol. 94(4), pages 677-691, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:10:y:2022:i:22:p:4367-:d:978460. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.