Tight bounds on exploration of constantly connected cacti-paths

In this paper, we study the necessary and sufficient time to explore constantly connected dynamics graphs by a mobile entity (agent). A dynamic graph is constantly connected if for each time units, there exists a stable connected spanning tree [10]. We focus on the case where the underlying graph is a cactus-path (graph reduced to a path of rings in which two neighbor rings have at most one vertex in common) and we assume that the agent knows the dynamics of the graph. We show that time units are necessary and sufficient to explore any constantly connected dynamic graph based on the cactus-path (composed of two same size rings). The upper bound is generalized on dynamic graphs based on cacti-paths with rings. We show that for any constantly connected dynamic graph of size based on a cactus-path, time units are sufficient to explore the graph, with the length of the path, the size of the dynamic graph and the size of the ring which is at position starting from left to right.