Temporal graphs (or evolving graphs) are time-varying graphs where time is assumed to be discrete. In this paper, we consider for the first time the problem of exploring temporal graphs of arbitrary unknown topology. We study the feasibility of exploration, under both the Fsync and Ssync schedulers, focusing on the number of agents necessary and sufficient to explore such graphs. We first consider the minimal (i.e., less restrictive) assumption on the dynamics of the graph under which exploration is still feasible: temporal connectivity. Let ℋ be the class of temporally connected graphs; we show that for any temporal graph ? ∈ ℋ the number of agents sufficient to perform exploration is related to the number of its transient edges, a parameter η(?) we call evanescence of the graph. More precisely, any ? ∈ ℋ can be explored by a team of k ≥ 2 η(?) +1 agents; this bound is tight as we prove there are ? ∈ ℋ that cannot be explored by 2 η(?) agents. We then turn our attention to the well-known stronger assumption on the dynamics of the graph, called 1-interval connectivity: the graph is connected at any time step. Let ? ⊂ ℋ be the class of these always-connected temporal graphs. For this class, we prove the existence of a difference between Fsync and Ssync when there is a bound ? on the number of edges missing at each time. In fact, we show a tight bound of 2 ? +1 on the number of agents necessary and sufficient in Ssync, and a smaller tight bound of 2 ? in Fsync. As a corollary, we re-establish two recently published bounds for 1-interval connected rings.

Mobile agents (agents) are activities which can move autonomously in a networked system and execute actions at visited nodes. One of the most fundamental problems of agents is exploration, which requires that each node should be visited by at least one agent. For a long time, researchers focus on exploration of static networks. However, exploration of dynamic networks comes to be studied recently. In this paper, we consider exploration of a dynamic torus under some constraints on the dynamics (or topology changes). An n × m torus (3 ≤ n ≤ m) is considered as a collection of n row rings and m column rings. The constraint on the dynamics is that each ring should be 1-interval connected, which allows at most one link to be missing at any time in each ring. On this n × m dynamic torus, we propose exploration algorithms with and without the link presence detection. With the link presence detection, an agent can detect which incident links are missing (if exist) before determining its next move. On the other hand, without the link presence detection, an agent has to determine its next move without knowing which incident links are missing, which makes the agent stay on the same node when the link necessary to the move is missing. We prove for exploration of the n × m dynamic torus that, without the link presence detection, n+1 agents are necessary and sufficient, and, with the link presence detection, ⌈n/2⌉ + 1 agents are necessary and sufficient. Moreover, for both cases, we propose asymptotically optimal algorithms with respect to both the numbers of agents and rounds when n = m.