The search value of a network
Steve Alpern, Miroslav D. Ašić · Networks · 1985
Abstract Let Q be a connected network with a distinguished (starting) point q0, 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 q0 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) ≦ 6kD for a network with k edges and diameter D.