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

DOI10.1007/S10255-022-1109-1MaRDI QIDQ2155657zbMATH OpenOpenAlexFDO

Authors Ming-rui Liu, Mei Lu

Publication date 15 July 2022

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

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)

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}^{\ast }$-free) to get a similar conclusion about the case of undirected graph.

Recommendations

• The cops and robber game on graphs with forbidden (induced) subgraphs
• Variations on cops and robbers
• Cops and robbers on oriented graphs
• Cops and Robbers on Planar‐Directed Graphs
• scientific article; zbMATH DE number 5241699

Cites work

• scientific article; zbMATH DE number 1665333 (Why is no real title available?)
• A bound for the cops and robbers problem
• A game of cops and robbers
• A short note about pursuit games played on a graph with a given genus
• Cops and Robbers on Planar‐Directed Graphs
• Cops and robbers in graphs with large girth and Cayley graphs
• On Meyniel's conjecture of the cop number
• On a pursuit game on Cayley digraphs
• The cops and robber game on graphs with forbidden (induced) subgraphs
• Variations on cops and robbers
• Vertex-to-vertex pursuit in a graph
• WHAT IS...Cop Number?

Cited in

(6)

• The cops and robber game on graphs with forbidden (induced) subgraphs
• Generalized cops and robbers: a multi-player pursuit game on graphs
• Cops and robbers on graphs with a set of forbidden induced subgraphs
• 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
• Cops and robbers on oriented 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)