How to Hunt an Invisible Rabbit on a Graph

Fedor V. Fomin; Micha{\l} Pilipczuk; Petr A. Golovach; Tatjana V. Abramovskaya

REVIEW

How to Hunt an Invisible Rabbit on a Graph

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1502.05614 v2 pith:UKPQHDLK submitted 2015-02-19 math.CO cs.DM

Tatjana V. Abramovskaya , Fedor V. Fomin , Petr A. Golovach , Micha{l} Pilipczuk This is my paper · ORCID

classification math.COcs.DM

keywords huntersrabbitgraphinvisiblenumberalongcatchedges

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

read the original abstract

We investigate Hunters & Rabbit game, where a set of hunters tries to catch an invisible rabbit that slides along the edges of a graph. We show that the minimum number of hunters required to win on an (n\times m)-grid is \lfloor min{n,m}/2\rfloor+1. We also show that the extremal value of this number on n-vertex trees is between \Omega(log n/log log n) and O(log n).

Discussion (0). Continue with ORCID to comment.

Pith tools