A Brightwell-Winkler type characterisation of NU graphs

In 2000, Brightwell and Winkler characterised dismantlable graphs as the graphs $H$ for which the Hom-graph $\mathrm{H}\mathrm{o}\mathrm{m}(G,H)$, defined on the set of homomorphisms from $G$ to $H$, is connected for all graphs $G$. This shows that the reconfiguration version $\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{o}{\mathrm{n}}_{\mathrm{H}\mathrm{o}\mathrm{m}}(H)$ of the $H$-colouring problem, in which one must decide for a given $G$ whether $\mathrm{H}\mathrm{o}\mathrm{m}(G,H)$ is connected, is trivial if and only if $H$ is dismantlable. We prove a similar starting point for the reconfiguration version of the $H$-extension problem. Where $\mathrm{H}\mathrm{o}\mathrm{m}(G,H;p)$ is the subgraph of the Hom-graph $\mathrm{H}\mathrm{o}\mathrm{m}(G,H)$ induced by the $H$-colourings extending the $H$-precolouring $p$ of $G$, the reconfiguration version $\mathrm{R}\mathrm{e}\mathrm{c}\mathrm{o}{\mathrm{n}}_{\mathrm{E}\mathrm{x}\mathrm{t}}(\mathrm{H})$ of the $H$-extension problem asks, for a given $H$-precolouring $p$ of a graph $G$, if $\mathrm{H}\mathrm{o}\mathrm{m}(G,H;p)$ is connected. We show that the graphs $H$ for which $\mathrm{H}\mathrm{o}\mathrm{m}(G,H;p)$ is connected for every choice of $(G,p)$ are exactly the $\mathrm{N}\mathrm{U}$ graphs. This gives a new characterisation of $\mathrm{N}\mathrm{U}$ graphs, a nice class of graphs that is important in the algebraic approach to the $\mathrm{C}\mathrm{S}\mathrm{P}$-dichotomy. We further give bounds on the diameter of $\mathrm{H}\mathrm{o}\mathrm{m}(G,H;p)$ for $\mathrm{N}\mathrm{U}$ graphs $H$, and show that shortest path between two vertices of $\mathrm{H}\mathrm{o}\mathrm{m}(G,H;p)$ can be found in parameterised polynomial time. We apply our results to the problem of shortest path reconfiguration, significantly extending recent results.