Cuts, Cats, and Complete Graphs

2024/09/20 by Rylo Ashmore, Danny Dyer, Ashmore, Rylo +5
Computer Science · #05C57 (Primary) 91A24 #68R05 (Secondary) #91A46 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.2409.13685

openalex publication_date 2024/09/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce the game of Cat Herding, where an omnipresent herder slowly cuts down a graph until an evasive cat player has nowhere to go. The number of cuts made is the score of a game, and we study the score under optimal play. In this paper, we begin by deriving some general results, and then we determine the precise cat number for paths, cycles, stars, and wheels. Finally, we identify an optimal Cat and Herder strategy on complete graphs, while providing both a recurrence and closed form for cat(K_n).

Related

• Extremal Cat Herding
• Undirected Cat-and-Mouse is P-complete
• Catching a mouse on a tree
• The Cat and the Noisy Mouse
• The Explorer-Director Game on Graphs