Pursuit—Evasion games on graphs

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 .