The Cop Number of Graphs with Forbidden Induced Subgraphs

MaRDI QIDQ6324407zbMATH OpenFDO

Authors Ming-rui Liu

Publication date 29 August 2019

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57)

Abstract: In the game of Cops and Robber, a team of cops attempts to capture a robber on a graph $G$. Initially, all cops occupy some vertices in $G$ and the robber occupies another vertex. In each round, a cop can move to one of its neighbors or stay idle, after which the robber does the same. The robber is caught by a cop if the cop lands on the same vertex which is currently occupied by the robber. The minimum number of cops needed to guarantee capture of a robber on $G$ is called the {em cop number} of $G$, denoted by $c(G)$. We say a family $calF$ of graphs is {em cop-bounded} if there is a constant $M$ so that $c(G)leqM$ for every graph $GincalF$. Joret, Kamin'nski, and Theis [Contrib. Discrete Math. 2010] proved that the class of all graphs not containing a graph $H$ as an induced subgraph is cop-bounded if and only if $H$ is a linear forest; morerover, $C(G)leqk-2$ if if $G$ is induced-$P_k$-free for $kgeq3$. In this paper, we consider the cop number of a family of graphs forbidding certain two graphs and generalized some previous results.

This page was built for publication: The Cop Number of Graphs with Forbidden Induced Subgraphs

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