Premium
Pursuit—Evasion games on graphs
Author(s) -
Chung F. R. K.,
Cohen Joel E.,
Graham R. L.
Publication year - 1988
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190120205
Subject(s) - pursuit evasion , counterintuitive , combinatorics , mathematics , vertex (graph theory) , graph , vertex connectivity , discrete mathematics , mathematical optimization , philosophy , epistemology
Two players, Red and Blue, each independently choose a vertex of a connected graph G . Red must then pay Blue an amount equal to the distance between the vertices chosen. In this note, we investigate the value ν( G )of this pursuit‐evasion game for various classes of graphs G , as well as those optimal mixed strategies for achieving ν( G ). It is shown that some rather counterintuitive behavior can occur. For example, there exist graphs G in which, for any optimal mixed strategy, Red never selects a vertex in the center of G .