Cop numbers for subclasses of partial cubes
The game of Cops and Robbers is a classical pursuit--evasion game on graphs. For a graph $G$, the cop number $c(G)$ is the minimum number of cops needed to guarantee the capture of a robber on $G$. Although this parameter has been determined for several fundamental graph classes, comparatively few exact results are known for partial cubes and their subclasses. We first establish an upper bound for every finite median graph $M$ in terms of its tree-dimension, which improves Crawford and Iršič Chenoweth's bound significantly. This result refines the previous upper bound expressed in terms of a…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.25416
curl -X POST /api/v1/records/arxiv/2608.25416/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.25416/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'