  We propose a Kuramoto model of coupled oscillators on a time-varying graph,
whose dynamics is dictated by a Markov process in the space of graphs. The
simplest representative is considering a base graph and then the subgraph
determined by $N$ independent random walks on the underlying graph. We prove a
synchronization result for solutions starting from a phase-cohesive set
independent of the speed of the random walkers, an averaging principle and a
global synchronization result with high probability for sufficiently fast
processes. We also consider Kuramoto oscillators in a dynamical version of the
Random Conductance Model.
