The Game of Cops and Robbers on Directed Graphs with Forbidden Subgraphs  

作　　者：Ming-rui LIU Mei LU 

机构地区：[1]Department of Mathematical Sciences,Tsinghua University,Beijing 100084,China

出　　处：《Acta Mathematicae Applicatae Sinica》2022年第3期684-689,共6页应用数学学报（英文版）

摘　　要：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 H^(-)-free digraphs. However, it is not the same as the case of undirected graph. So we give a new concept(H^(-)^(*)-free digraph) to get a similar conclusion about the case of undirected graph.

关 键 词：cops and robbers directed graph induced subgraphs 

分 类 号：O157.5[理学—数学]