# Cover Time in Edge-Uniform Stochastically-Evolving Graphs +
## 8 Conclusions  
We defined the general edge-uniform evolution model for a stochastically-evolving graph, where a single stochastic rule is applied, but to each edge independently, and provided lower and upper bounds for the cover time of two random walks taking place on such a graph (cases \(k=0,1\)). Moreover, we provided a general framework to compute the exact cover time of a broad family of stochastically-evolving graphs in exponential time. An immediate open question is how to obtain a good lower/upper bound for the cover time of RWA in the birth-death model. In this case, the problem becomes quite more complex than the \(k=0\) case. Depending on the values of \(p\) and \(q\), the walk may be heavily biased, positively or negatively, toward possible edges incident to the walker's position, which were used in the recent past. The source code associated with the experiments in Section 7 is available online at [[https://github.com/yiannislamprou/AvgRWA](https://github.com/yiannislamprou/AvgRWA)]([https://github.com/yiannislamprou/AvgRWA](https://github.com/yiannislamprou/AvgRWA)). All authors contributed both to the research work and the writing of this paper. This research was partially supported by the Network Sciences and Technologies (NeST) initiative of the School of Electrical Engineering, Electronics and Computer Science at the University of Liverpool. [PERSON] was partially funded by EPSRC grant number EP/P02002X/1 \"Algorithmic Aspects of Temporal Graphs\". \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Size** & \(\delta\) & \(\Delta\) & \(p\) & **Static Cover Time** & **Temporal Cover Time** & **Lower Bound** & **Upper Bound** \\ \hline
10 & 2 & 5 & 0.9 & 38 & 38 & 38 \\
10 & 1 & 5 & 0.5 & 62 & 70 & 64 & 125 \\
10 & 2 & 4 & 0.2 & 41 & 88 & 69 & 113 \\
10 & 2 & 5 & 0.1 & 48 & 176 & 117 & 252 \\
10 & 1 & 5 & 0.05 & 46 & 361 & 203 & 919 \\
10 & 2 & 4 & 0.01 & 38 & 1356 & 959 & 1899 \\ \hline
100 & 9 & 28 & 0.9 & 671 & 671 & 671 & 671 \\
100 & 8 & 24 & 0.1 & 634 & 740 & 689 & 1113 \\
100 & 11 & 25 & 0.05 & 616 & 1033 & 852 & 1428 \\
100 & 9 & 24 & 0.01 & 694 & 4152 & 3240 & 8028 \\
100 & 10 & 23 & 0.005 & 642 & 7873 & 5894 & 13127 \\ \hline
250 & 25 & 57 & 0.9 & 1708 & 1708 & 1708 & 1708 \\
250 & 27 & 59 & 0.1 & 1700 & 1739 & 1700 & 1803 \\
250 & 23 & 54 & 0.01 & 1750 & 5167 & 4179 & 8480 \\
250 & 23 & 54 & 0.005 & 1736 & 9601 & 7321 & 15944 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Experimental results for randomly-produced graphs (\(randomThreshold=0.15\)). \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Size** & \(\delta\) & \(\Delta\) & \(p\) & **Static Cover Time** & **Temporal Cover Time** & **Lower Bound** & **Upper Bound** \\ \hline
10 & 3 & 6 & 0.9 & 35 & 35 & 35 & 35 \\
10 & 3 & 7 & 0.5 & 33 & 35 & 34 & 38 \\
10 & 5 & 8 & 0.2 & 28 & 37 & 33 & 41 \\
10 & 4 & 8 & 0.1 & 34 & 69 & 60 & 100 \\
10 & 3 & 8 & 0.05 & 32 & 118 & 96 & 226 \\
10 & 3 & 7 & 0.01 & 33 & 780 & 486 & 1113 \\ \hline
100 & 39 & 60 & 0.9 & 542 & 542 & 542 & 542 \\
100 & 37 & 68 & 0.1 & 561 & 571 & 561 & 572 \\
100 & 35 & 63 & 0.05 & 556 & 589 & 579 & 667 \\
100 & 38 & 63 & 0.01 & 544 & 1349 & 1160 & 1714 \\
100 & 35 & 61 & 0.005 & 549 & 2436 & 2085 & 3413 \\ \hline
250 & 106 & 144 & 0.9 & 1589 & 1589 & 1589 & 1589 \\
250 & 105 & 145 & 0.025 & 1581 & 1646 & 1623 & 1700 \\
250 & 109 & 147 & 0.01 & 1579 & 2150 & 2046 & 2372 \\
250 & 105 & 150 & 0.005 & 1584 & 3324 & 2998 & 3871 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Experimental results for randomly-produced graphs (\(randomThreshold=0.5\)). **Acknowledgments:** We acknowledge two anonymous reviewers for spotting technical errors in the previously attempted analysis of the one-step history RWA. Furthermore, we acknowledge another anonymous reviewer who suggested using Theorem 2 as an alternative to electrical network theory and some other modifications. **Conflicts of Interest:** The authors declare no conflict of interest.