On quantum superpositions of graphs, no-signalling and covariance

We provide a mathematically and conceptually robust notion of quantum superpositions of graphs. We argue that, crucially, quantum superpositions of graphs require node names for their correct alignment, which we demonstrate through a no-signalling argument. Nevertheless, node names are a fiducial construct, serving a similar purpose to the labelling of points through a choice of coordinates in continuous space. Graph renamings are understood as a change of coordinates on the graph and correspond to a natively discrete analogue of diffeomorphisms. We postulate renaming invariance as a symmetry principle in discrete topology of similar weight to diffeomorphism invariance in the continuous. We show how to impose renaming invariance at the level of quantum superpositions of graphs.