COVERING REGULAR GRAPHS

A covering projection from a graph G onto a graph H is a ''local isomo rphism'': a mapping From the vertex set of G onto the vertex set of H such that, for every upsilon is an element of V(G), the neighborhood o f upsilon is mapped bijectively onto the neighborhood (in H) of the im age of upsilon. We investigate two concepts that concern graph covers of regular graphs. The first one is called ''multicovers'': we show th at for any regular graph H there exists a graph G that allows many dif ferent covering projections onto H. Secondly, we consider partial cove rs, which require only that G be a subgraph of a cover of X. As an app lication of our results we show that there are infinitely many rigid r egular graphs H for which the H-cover problem-deciding if a given grap h G covers H-is NP-complete. This resolves an open problem related to the characterization of graphs H for which H-COVER is tractable. (C) 1 997 Academic Press.