Throttling for the game of Cops and Robbers on graphs
| Autor: | Leslie Hogben, Joshua Carlson, Boris Brimkov, Jane Breen, K. E. Perry, Carolyn Reinhart |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
010102 general mathematics 0102 computer and information sciences Bandwidth throttling Positive-definite matrix 01 natural sciences Upper and lower bounds Graph Theoretical Computer Science Combinatorics 010201 computation theory & mathematics Bounding overwatch Zero Forcing Equalizer Discrete Mathematics and Combinatorics Hypercube Projective plane 0101 mathematics Mathematics |
| Zdroj: | Discrete Mathematics. 341:2418-2430 |
| ISSN: | 0012-365X |
| DOI: | 10.1016/j.disc.2018.05.017 |
| Popis: | We consider the cop-throttling number of a graph G for the game of Cops and Robbers, which is defined to be the minimum of ( k + capt k ( G ) ) , where k is the number of cops and capt k ( G ) is the minimum number of rounds needed for k cops to capture the robber on G over all possible games. We provide some tools for bounding the cop-throttling number, including showing that the positive semidefinite (PSD) throttling number, a variant of zero forcing throttling, is an upper bound for the cop-throttling number. We also characterize graphs having low cop-throttling number and investigate how large the cop-throttling number can be for a given graph. We consider trees, unicyclic graphs, incidence graphs of finite projective planes (a Meyniel extremal family of graphs), a family of cop-win graphs with maximum capture time, grids, and hypercubes. All the upper bounds on the cop-throttling number we obtain for families of graphs are O ( n ) . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect