Covering regular graphs (Q1386472)

A covering projection from a graph \(G\) onto a graph \(H\) is a ``local isomorphism'': a mapping from the vertex set of \(G\) onto the vertex set of \(H\) such that, for every \(v\in V(G)\), the neighborhood of \(v\) is mapped bijectively onto the neighborhood (in \(H\)) of the image of \(v\). The authors investigate two concepts that concern graph covers of regular graphs. The first one is called ``multicover'': they show that for any regular graph \(H\) there exists a graph \(G\) that allows many different covering projections onto \(H\). Secondly, they consider partial covers, which require only that \(G\) be a subgraph of a cover of \(H\). As an application of their results they show that there are infinitely many rigid regular graphs \(H\) for which the \(H\)-cover problem---deciding if a given graph \(G\) covers \(H\)---is NP-complete. This resolves an open problem related to the characterization of graphs \(H\) for which \(H\)-COVER is tractable.