  This paper considers non-backtracking random walks on random graphs generated
according to the configuration model. The quantity of interest is the scaling
of the mixing time of the random walk as the number of vertices of the random
graph tends to infinity. Subject to mild general conditions, we link two mixing
times: one for a static version of the random graph, the other for a class of
dynamic versions of the random graph in which the edges are randomly rewired
but the degrees are preserved. The link is provided by the probability that the
random walk has not yet stepped along a previously rewired edge. We use this
link to compute the scaling of the mixing time for three specific classes of
random rewirings. Depending on the speed and the range of the rewiring relative
to the current location of the random walk, the mixing time may exhibit no
cut-off, one-sided cut-off or two-sided cut-off, a trichotomy that was also
found in earlier work. Interestingly, for a class of dynamics that are
`mesoscopic', i.e., non-local and non-global, we find new behaviour with six
subregimes. Proofs are built on a new and flexible coupling scheme, in
combination with sharp estimates on the degrees encountered by the random walk
in the static and the dynamic version of the random graph. Some of these
estimates require sharp control on possible short-cuts in the graph between the
edges that are traversed by the random walk.
