We present the following results for this problem.
1- Fault tolerant DFS tree
There exists a data structure of size $O(m\log n)$ such that given any
$k$ updates, a DFS tree for the
resulting graph can be reported in
\tilde{O}(nk) (hiding the poly-logarithmic factors.)
worst case time. When the $k$ updates are deletions only, this
directly implies an $\tilde{O}(nk)$ time fault
tolerant algorithm for a DFS tree.
2- Fully dynamic DFS tree
There exists a fully dynamic algorithm for maintaining a DFS tree that
takes worst case $\tilde{O}(\sqrt{mn})$
time per update for any arbitrary online sequence of updates.
Our results are the first $o(m)$ worst case time results for
maintaining a DFS tree in a dynamic setting.
Our fully dynamic algorithm provides, in a seamless manner, the first
non-trivial algorithm with $O(1)$ query time
and $o(m)$ worst case update time for the dynamic subgraph
connectivity, bi-connectivity, 2 edge-connectivity.
We also present the conditional lower bound of $\Omega(n)$ time per
update for maintenance of a DFS tree.