# Cover Time in Edge-Uniform Stochastically-Evolving Graphs +
## 6 An Exact Approach  
So far, we have established upper and lower bounds for the cover time of edge-uniform stochastically-evolving graphs. Our bounds are based on combining extended results from simple random walk theory and careful delay estimations. In this section, we describe an approach to determine the exact cover time for temporal graphs evolving under any stochastic model. Then, we apply this approach to the already seen zero-step history and one-step history cases of RWA. The key component of our approach is a Markov chain capturing both phases of evolution: the graph dynamics and the walk trajectory. In that case, calculating the cover time reduces to calculating the hitting time to a particular subset of Markov states. Although computationally intractable for large graphs, such an approach provides the exact cover time value and is hence practical for smaller graphs. Suppose we are given an underlying graph \(G=(V,E)\) and a set of stochastic rules \(R\) capturing the evolution dynamics of \(G\). That is, \(R\) can be seen as a collection of probabilities of transition from one graph instance to another. We denote by \(k\) the (longest) history length taken into account by the stochastic rules. Like before, let \(n=|V|\) stand for the number of nodes and \(m=|E|\) for the number of possible edges of \(G\). We define a Markov chain \(M\) with states of the form \((H,v,V_{c})\), where:  
* \(H=(H_{1},H_{2},\ldots,H_{k})\) is a \(k\)-tuple of temporal graph instances, that is for each \(i=1,2,\ldots,k\), \(H_{i}\) is the graph instance present \(i-1\) time steps before the current one (which is \(H_{1}\))
* \(v\in V(G)\) is the current position of the agent
* \(V_{c}\subseteq V(G)\) is the set of already covered nodes, i.e., the set of nodes that have been visited at least once by the agent  
As described earlier for our edge-uniform model, we assume evolution happens in two phases. First, the new graph instance is determined according to the rule-set \(R\). Second, the new agent position is determined based on a random walk on what is available. In this respect, consider a state \(S=(H,v,V_{c})\) and another state \(S^{\prime}=(H^{\prime},v^{\prime},V^{\prime}_{c})\) of the described Markov chain \(M\). Let \(\Pr[S\to S^{\prime}]\) denote the transition probability from \(S\) to \(S^{\prime}\). We seek to express this probability as a product of the probabilities for the two phases of evolution. The latter is possible, since, in our model, the random walk strategy is independent of the graph evolution. For the graph dynamics, let \(\Pr[H\stackrel{{ R}}{{\rightarrow}}H^{\prime}]\) stand for the probability to move from a history-tuple \(H\) to another history-tuple \(H^{\prime}\) under the rules of evolution in \(R\). Note that, for \(i=1,2,\ldots,k-1\), it must hold \(H^{\prime}_{i+1}=H_{i}\) in order to properly maintain history, otherwise the probability becomes zero. On the other hand, for valid transitions, the probability reduces to \(\Pr[H^{\prime}_{1}|(H_{1},H_{2},\ldots,H_{k})]\), which is exactly the probability that \(H^{\prime}_{1}\) becomes the new instance given the history \(H=(H_{1},H_{2},\ldots,H_{k})\) of past instances (and any such probability is either given directly or implied by \(R\)). For the second phase, i.e., the random walk on what is available, we denote by \(\Pr[v\stackrel{{ H_{i}}}{{\rightarrow}}v^{\prime}]\) the probability of moving from \(v\) to \(v^{\prime}\) on some graph instance \(H_{j}\). Since the random walk strategy is only based on the current instance, we can derive a general expression for this probability, which is independent of the graph dynamics \(R\). Below, let \(N_{H_{j}}(v)\) stand for the set of neighbours of \(v\) in graph instance \(H_{j}\). If \(\{v,v^{\prime}\}\
ot\in E(G)\), that is if there is no possible edge between \(v\) and \(v^{\prime}\), then for any temporal graph instance \(H_{j}\), it holds \(\Pr[v\stackrel{{ H_{j}}}{{\rightarrow}}v^{\prime}]=0\).