  The Kuramoto model of coupled phase oscillators on small-world (SW) graphs is
analyzed in this work. When the number of oscillators in the network goes to
infinity, the model acquires a family of steady state solutions of degree q,
called q-twisted states. We show that this class of solutions plays an
important role in the formation of spatial patterns in the Kuramoto model on SW
graphs. In particular, the analysis of q-twisted elucidates the role of
long-range random connections in shaping the attractors in this model.
  We develop two complementary approaches for studying q-twisted states in the
coupled oscillator model on SW graphs: the linear stability analysis and the
numerical continuation. The former approach shows that long-range random
connections in the SW graphs promote synchronization and yields the estimate of
the synchronization rate as a function of the SW randomization parameter. The
continuation shows that the increase of the long-range connections results in
patterns consisting of one or several plateaus separated by sharp interfaces.
  These results elucidate the pattern formation mechanisms in nonlocally
coupled dynamical systems on random graphs.
