Covering graph

In the mathematical discipline of graph theory, a graph C is a covering graph of another graph G if there is a covering map from the vertex set of C to the vertex set of G. A covering map f is a surjection and a local isomorphism: the neighbourhood of a v vertex in C is mapped bijectively onto the neighbourhood of f(v) in G.

The term lift is often used synonymous for a covering graph of a connected graph.

In graph theory, a covering graph may also refer to a subgraph that contains either all edges (edge cover) or all vertexes (vertex cover).

The combinatorial formulation of covering graph is immediately generalized to the case of multigraph. If we identify a multigraph with a 1-dimensional cell complex, a covering graph is nothing but a special example of covering spaces of topological spaces, so that the terminology in the theory of covering spaces is available; say covering transformation group, universal covering, abelian covering, and maximal abelian covering.

Let G = (V₁, E₁) and C = (V₂, E₂) be two graphs, and let f: V₂ → V₁ be a surjection. Then f is a covering map from C to G if for each v ∈ V₂, the restriction of f to the neighbourhood of v is a bijection onto the neighbourhood of f(v) in G. Put otherwise, f maps edges incident to v one-to-one onto edges incident to f(v).

If there exists a covering map from C to G, then C is a covering graph, or a lift, of G. An h-lift is a lift such that the covering map f has the property that for every vertex v of G, its fiber f⁻¹(v) has exactly h elements.

...
Wikipedia