I know from [1] that the lower bound for the maximum hitting time of simple random walk on a dynamic graph is $\Omega(2^n)$. Smoothed analysis has been applied to the maximum hitting time [3] and gives us a $k$-smoothed lower bound of $\Omega(n^{5/2}/\sqrt{k}\log{n})$; a significantly weaker lower bound.
In [3] they give a $k$-smoothed lower bound for flooding of $\Omega(n^{2/3}/k^{1/3})$, where the non-smoothed lower bound is $\Omega(n)$. They also state
There are many additional interesting dynamic network bounds that could be subjected to a smoothed analysis.
In [2] they give a lower bound of $\Omega(nk/\log{n})$ for solving the 𝑘-gossip problem on dynamic graphs. But do not give a smoothed version of it. This could thus be a candidate for smoothing.
I have also heard of the load balancing problem, where each node $v$ is given $w(v)$ tokens, and the goal is to balance the tokens amongst all the nodes so that $\max_{u\in V}|w_u - w_{avg}|$ is minimized. I am not aware of any unsmoothed lower bounds for this problem on dynamic graphs, but this could also be a candidate.
Finally, leader election in dynamic graphs which in each round are always connected could be studied. Although I am not aware of any existing lower bounds.
I want to know which other problems/properties of dynamic graphs, like the maximum hitting time, have strong lower bounds, indicating that a $k$-smoothed lower bound may be much weaker.
Background:
A dynamic graph $H$ is a sequence of static graphs $H=(G_1,G_2,...)$ on an unchanging set of vertices $V$. $H$ evolves in rounds, where in round $i$, $H$ takes the structure of $G_i=(V,E_i)$.
The lower bound for the hitting time assumes $H$ is selected from a family of dynamic graphs were each static graph is connected.
$k$-smoothing a dynamic graph $H$ belonging to a family of dynamic graphs $F$, means replacing every $G_i\in H$ with $G_i'\in\text{editdist}(G_i,k)\cap\{G|H\in F \text{ and }G\in H\}$. The set $\text{editdist}(G,k)$ is the set of static graphs which can be reached from $G$ by adding or removing at most $k$ edges.
[1] How to Explore a Fast-Changing World. Chen Avin, Michal Koucký, and Zvi Lotker.
[2] Information Spreading in Dynamic Networks. Chinmoy Dutta, Gopal Pandurangan, Rajmohan Rajaraman, Zhifeng Sun
[3] Smoothed Analysis of Dynamic Networks. Michael Dinitz, Jeremy T. Fineman