In this paper we present the Relay Chain: a new algorithm central to a novel strategy for exploring underwater environments using a swarm of autonomous underwater vehicles (AUVs). The Relay Chain provides a mobile, scalable and dynamic communication link between the water's surface and a shoal of AUVs exploring the sea bed. The chain tracks the shoal as it explores, recruiting and returning AUVs from and to the shoal to modulate the length of the chain as required. The chain can instruct the shoal to reverse course when it travels too far from the starting point and there are no further AUVs to recruit. Given the challenging underwater environment, chain breakages are however inevitable, and as such we consider a number of recovery strategies to address chain breakages and minimise the time for which messages destined to the surface from the shoal are delayed. A simple 'turn and search' strategy is contrasted with strategies that depend on absolute positioning systems of varying accuracy. Implementing underwater absolute positioning systems is challenging, and our results highlight how accurate such a system must be to outperform more naive strategies, and hence be considered a worthwhile investment. We find the accuracy must be within 20cm, being 40% of AUV sensor range.