  Given the recent advances in quantum technology, the complexity of quantum
states is an important notion. The idea of the Krylov spread complexity has
come into focus recently with the goal of capturing this in a quantitative way.
The present paper sheds new light on the Krylov complexity measure by exploring
it in the context of continuous-time quantum-walks on graphs. A close
relationship between Krylov spread complexity and the concept of
limiting-distributions for quantum-walks is established. Moreover, using a
graph optimization algorithm, quantum-walk graphs are constructed that have
minimal and maximal long-time average Krylov $\bar C$-complexity. This reveals
an empirical upper bound for the $\bar C$-complexity as a function of Hilbert
space dimension and an exact lower bound.
