The search value of a network

Abstract

Abstract Let Q be a connected network with a distinguished (starting) point q 0 , whose are lengths sum to one. We associate with Q a “search value” V( Q ) representing the expected time needed for a searcher, starting at q 0 and moving at unit speed, to find a moving hider. We assume neither sees the other until they meet. We demonstrate that the “figure‐eight” network, consisting of two equal loops joined at a central starting point, has a search value not exceeding 15/16. This contradicts a conjecture of Gal that the search value of any network is at least 1. In the other direction, we show that V( Q ) ≦ 6 kD for a network with k edges and diameter D .