The game of cops and robbers on directed graphs with forbidden subgraphs

DOI10.1007/S10255-022-1109-1zbMATH Open1492.05101arXiv2001.09853OpenAlexW3003028482MaRDI QIDQ2155657FDOQ2155657

Ming-rui Liu, Mei Lu

Publication date: 15 July 2022

Published in: Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

Abstract: The traditional game of cops and robbers is played on undirected graph. Recently, the same game played on directed graph is getting attention by more and more people. We knew that if we forbid some subgraph we can bound the cop number of the corresponding class of graphs. In this paper, we analyze the game of cops and robbers on $VecH$-free digraphs. However, it is not the same as the case of undirected graph. So we give a new concept ($Vec{H}^{*}$-free) to get a similar conclusion about the case of undirected graph.

Full work available at URL: https://arxiv.org/abs/2001.09853

zbMATH Keywords

cops and robbersdirected graphinduced subgraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Cites Work

• Cops and robbers in graphs with large girth and Cayley graphs
• Vertex-to-vertex pursuit in a graph
• Variations on cops and robbers
• On Meyniel's conjecture of the cop number
• A Bound for the Cops and Robbers Problem
• A game of cops and robbers
• WHAT IS...Cop Number?
• A short note about pursuit games played on a graph with a given genus
• Title not available (Why is that?)
• On a pursuit game on Cayley digraphs
• Cops and Robbers on Planar‐Directed Graphs
• The Cops and Robber game on graphs with forbidden (induced) subgraphs

Cited In (3)

• Generalized cops and robbers: a multi-player pursuit game on graphs
• Cops and Robber game with a fast robber on expander graphs and random graphs
• The impact of loops on the game of cops and robbers on graphs

This page was built for publication: The game of cops and robbers on directed graphs with forbidden subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2155657)