Cops and robbers on graphs with a set of forbidden induced subgraphs

DOI10.1016/J.TCS.2020.06.032MaRDI QIDQ2196576zbMATH OpenOpenAlexFDO

Authors Masood Masjoody, Ladislav Stacho

Publication date 3 September 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

forbidden induced subgraphsgame of cops and robbersgeneralized clawgeneralized netgraph classesone-active cop game

Mathematics Subject Classification ID

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

Abstract: It is known 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 forest whose every component is a path. In this study, we characterize all sets $mathscrH$ of graphs with some $kinmathbbN$ bounding the diameter of members of $mathscrH$ from above, such that $mathscrH$-free graphs, i.e. graphs with no member of $mathscrH$ as an induced subgraph, are cop-bounded. This, in particular, gives a characterization of cop-bounded classes of graphs defined by a finite set of connected graphs as forbidden induced subgraphs. Furthermore, we extend our characterization to the case of cop-bounded classes of graphs defined by a set $mathscrH$ of forbidden graphs such that there is $kinmathbbN$ bounding the diameter of components of members of $mathscrH$ from above.

Recommendations

• The cops and robber game on graphs with forbidden (induced) subgraphs
• Cops and Robbers on Graphs of Bounded Diameter
• The game of cops and robbers on directed graphs with forbidden subgraphs
• A game of cops and robbers
• scientific article; zbMATH DE number 5241699

Cites work

• A game of cops and robbers
• Note on a pursuit game played on graphs
• On the cop number of a graph
• The cops and robber game on graphs with forbidden (induced) subgraphs
• The optimal capture time of the one-cop-moves game

Cited in

(8)

• Cops and robbers on \(2K_2\)-free graphs
• Cops and robber on subclasses of \(P_5\)-free graphs
• scientific article; zbMATH DE number 6820595 (Why is no real title available?)
• The cops and robber game on graphs with forbidden (induced) subgraphs
• scientific article; zbMATH DE number 7720718 (Why is no real title available?)
• Cops and Robbers on \(\boldsymbol{P_5}\)-Free Graphs
• Improved bounds on the cop number when forbidding a minor
• Cops and robbers, clique covers, and induced cycles

This page was built for publication: Cops and robbers on graphs with a set of forbidden induced subgraphs

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