  We consider random walks evolving on two models of connected and undirected
graphs and study the exact large deviations of a local dynamical observable. We
prove, in the thermodynamic limit, that this observable undergoes a first-order
dynamical phase transition (DPT). This is interpreted as a `co-existence' of
paths in the fluctuations that visit the highly connected bulk of the graph
(delocalization) and paths that visit the boundary (localization). The methods
we used also allow us to characterize analytically the scaling function that
describes the finite size crossover between the localized and delocalized
regimes. Remarkably, we also show that the DPT is robust with respect to a
change in the graph topology, which only plays a role in the crossover regime.
All results support the view that a first-order DPT may also appear in random
walks on infinite-size random graphs.
