๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Vertex-to-vertex pursuit in a graph

โœ Scribed by Richard Nowakowski; Peter Winkler

Book ID
103058406
Publisher
Elsevier Science
Year
1983
Tongue
English
Weight
612 KB
Volume
43
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

A graph G is given and two players, a cop and a robber, play the folioking game: the cop chooses a vertex, then the robber chooses a vertex, then the players move alternately beginning with the cop. A move consists of staying at one's present vertex or moving to an adjacent vertex; each move is seen by both players. The cop wins if he manages to occupy the same vertex as the robber, and the robber wins if he avoids this forever.

We characterize the graphs on which the cop has a winning strategy, and connect the problem with the structure theory of graphs based on products and retracts.

๐Ÿ“œ SIMILAR VOLUMES

Plane four-regular graphs with vertex-to
Plane four-regular graphs with vertex-to-vertex unit triangles
โœ Heiko Harborth ๐Ÿ“‚ Article ๐Ÿ“… 1991 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 215 KB

Harborth, H., Plane four-regular graphs with vertex-to-vertex unit triangles, Discrete Mathematics 97 (1991) 219-222. For the smallest number of non-overlapping vertex-to-vertex unit triangles in the plane it is proved ~42 in general, and <3800 if additional triangles are not allowed.

Vertex-disjoint chorded cycles in a grap
Vertex-disjoint chorded cycles in a graph
โœ Shengning Qiao; Shenggui Zhang ๐Ÿ“‚ Article ๐Ÿ“… 2010 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 208 KB
Vertex reconstruction in Cayley graphs
Vertex reconstruction in Cayley graphs
โœ Elena Konstantinova ๐Ÿ“‚ Article ๐Ÿ“… 2009 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 740 KB
On packing 3-vertex paths in a graph
On packing 3-vertex paths in a graph
โœ Atsushi Kaneko; Alexander Kelmans; Tsuyoshi Nishimura ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 276 KB ๐Ÿ‘ 2 views