Herding cats: a novel pursuit-evasion game

Abstract

In the game of Cat Herding on a graph, players alternate turns, with one player (the herder) omnipresently deleting edges, while the other player (the cat) begins on a vertex of the graph, and on each turn will move along any path to a new vertex. Eventually (for finite graphs), the cat is isolated on a single vertex; and the cat�s objective is to delay this event, while the herder tries to hasten it. In an optimally played (finite) game, the number of edge deletions the herder made to isolate the cat is the cat number of the graph, denoted cat(G). We investigate this graph parameter and graph dynamic from many different angles. We find the cat numbers of graphs from some common graph families. Some graphs we view asymptotically (trees, planar graphs), some we find efficiently-computable al- gorithms to compute the cat number (spiders), and some we solve with explicit closed forms (paths, cycles, stars, wheels, and complete graphs). We also look at the extremal instances of the game, characterizing the graphs of low cat numbers (cat(G) ? 3), and briefly introduce an infinite variant of the game, allowing varying levels at which the cat can win. From this, we provide a classification of those graphs where the cat or herder can win.