Centre for Discrete and Applicable Mathematics 

CDAM Research Report, LSECDAM200605March 2006 
Searching Symmetric Networks with Utilitarian Postman Paths
Steve Alpern, Vic Baston and Shmuel Gal
For any network Q, one may consider the zerosum search game G(Q) in which the (minimizing) Searcher picks a unit speed path S(t) in Q, the Hider picks a point H in Q and the payoff is the meeting time T = min {t: S(t)=H}.:We show first that if Q is symmetric (edge and vertex transitive), then it is optimal for the Hider to pick H uniformly in Q, so that the Searcher must follow a Utilitarian Postman path (one which minimizes the time to reach a random point). We then show that if Q is symmetric of odd degree, with n vertices and m unit length edges, the value V of G(Q) satisfies V>=m/2 + (n2n), with equality if and only if Q has a path e(1),...,e(n2) which includes n1 vertices such that Q  {e(2), e(4), ... , e(n2) is a connected set of edges.
A PDF file (228 kB) with the full contents of this report can be downloaded by clicking here.
Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSECDAM200605, together with your name and postal address to:
CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K. 

Phone: +44(0)207955 7494. Fax: +44(0)207955 6877. Email: info@maths.lse.ac.uk 
Introduction to the CDAM Research Report Series.  
CDAM Homepage. 