
arXiv: 1812.06230
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 $\mathscr{H}$ of graphs with some $k\in \mathbb{N}$ bounding the diameter of members of $\mathscr{H}$ from above, such that $\mathscr{H}$-free graphs, i.e. graphs with no member of $\mathscr{H}$ 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 $\mathscr{H}$ of forbidden graphs such that there is $k\in\mathbb{N}$ bounding the diameter of components of members of $\mathscr{H}$ from above.
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Games on graphs (graph-theoretic aspects), graph classes, 05C57, 91A46, generalized net, generalized claw, forbidden induced subgraphs, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Games involving graphs, game of cops and robbers, Positional games (pursuit and evasion, etc.), one-active cop game, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Games on graphs (graph-theoretic aspects), graph classes, 05C57, 91A46, generalized net, generalized claw, forbidden induced subgraphs, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Games involving graphs, game of cops and robbers, Positional games (pursuit and evasion, etc.), one-active cop game, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
