Interesting Esoterica

Catching a mouse on a tree

Article by Vytautas Gruslys and Arès Méroueh
  • Published in 2015
  • Added on
In this paper we consider a pursuit-evasion game on a graph. A team of cats, which may choose any vertex of the graph at any turn, tries to catch an invisible mouse, which is constrained to moving along the vertices of the graph. Our main focus shall be on trees. We prove that $\lceil (1/2)\log_2(n)\rceil$ cats can always catch a mouse on a tree of order $n$ and give a collection of trees where the mouse can avoid being caught by $ (1/4 - o(1))\log_2(n)$ cats.

Links

Other information

key
Catchingamouseonatree
type
article
date_added
2019-10-08
date_published
2015-09-30

BibTeX entry

@article{Catchingamouseonatree,
	key = {Catchingamouseonatree},
	type = {article},
	title = {Catching a mouse on a tree},
	author = {Vytautas Gruslys and Arès M{\'{e}}roueh},
	abstract = {In this paper we consider a pursuit-evasion game on a graph. A team of cats,
which may choose any vertex of the graph at any turn, tries to catch an
invisible mouse, which is constrained to moving along the vertices of the
graph. Our main focus shall be on trees. We prove that {\$}\lceil
(1/2)\log{\_}2(n)\rceil{\$} cats can always catch a mouse on a tree of order {\$}n{\$} and
give a collection of trees where the mouse can avoid being caught by {\$} (1/4 -
o(1))\log{\_}2(n){\$} cats.},
	comment = {},
	date_added = {2019-10-08},
	date_published = {2015-09-30},
	urls = {http://arxiv.org/abs/1502.06591v1,http://arxiv.org/pdf/1502.06591v1},
	collections = {Animals,Attention-grabbing titles,Combinatorics},
	url = {http://arxiv.org/abs/1502.06591v1 http://arxiv.org/pdf/1502.06591v1},
	year = 2015,
	urldate = {2019-10-08},
	archivePrefix = {arXiv},
	eprint = {1502.06591},
	primaryClass = {math.CO}
}