# 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 vertex *v* in *C* is mapped bijectively onto the neighbourhood of *f*(*v*) in *G*.

The term **lift** is often used as a synonym 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 graphs is immediately generalized to the case of multigraphs. 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.^{[1]}

## Contents

## DefinitionEdit

Let *G* = (*V*_{1}, *E*_{1}) and *C* = (*V*_{2}, *E*_{2}) be two graphs, and let *f*: *V*_{2} → *V*_{1} be a surjection. Then *f* is a *covering map* from *C* to *G* if for each *v* ∈ *V*_{2}, 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 ^{−1}(v)* has exactly

*h*elements.

## ExamplesEdit

In the following figure, the graph *C* is a covering graph of the graph *H*.

The covering map *f* from *C* to *H* is indicated with the colours. For example, both blue vertices of *C* are mapped to the blue vertex of *H*. The map *f* is a surjection: each vertex of *H* has a preimage in *C*. Furthermore, *f* maps bijectively each neighbourhood of a vertex *v* in *C* onto the neighbourhood of the vertex *f*(*v*) in *H*.

For example, let *v* be one of the purple vertices in *C*; it has two neighbours in *C*, a green vertex *u* and a blue vertex *t*. Similarly, let *v*′ be the purple vertex in *H*; it has two neighbours in *H*, the green vertex *u*′ and the blue vertex *t*′. The mapping *f* restricted to {*t*, *u*, *v*} is a bijection onto {*t*′, *u*′, *v*′}. This is illustrated in the following figure:

Similarly, we can check that the neighbourhood of a blue vertex in *C* is mapped one-to-one onto the neighbourhood of the blue vertex in *H*:

## Double coverEdit

In the above example, each vertex of *H* has exactly 2 preimages in *C*. Hence *H* is a *2-fold cover* or a *double cover* of *C*.

For any graph *G*, it is possible to construct the bipartite double cover of *G*, which is a bipartite graph and a double cover of *G*. The bipartite double cover of *G* is the tensor product of graphs *G* × *K*_{2}:

If *G* is already bipartite, its bipartite double cover consists of two disjoint copies of *G*. A graph may have many different double covers other than the bipartite double cover.

## Universal coverEdit

For any connected graph *G*, it is possible to construct its **universal covering graph**.^{[2]} This is an instance of the more general universal cover concept from topology; the topological requirement that a universal cover be simply connected translates in graph-theoretic terms to a requirement that it be acyclic and connected; that is, a tree.
The universal covering graph is unique (up to isomorphism). If *G* is a tree, then *G* itself is the universal covering graph of *G*. For any other finite connected graph *G*, the universal covering graph of *G* is a countably infinite (but locally finite) tree.

The universal covering graph *T* of a connected graph *G* can be constructed as follows. Choose an arbitrary vertex *r* of *G* as a starting point. Each vertex of *T* is a non-backtracking walk that begins from *r*, that is, a sequence *w* = (*r*, *v*_{1}, *v*_{2}, ..., *v*_{n}) of vertices of *G* such that

*v*_{i}and*v*_{i+1}are adjacent in*G*for all*i*, i.e.,*w*is a walk*v*_{i-1}≠*v*_{i+1}for all*i*, i.e., w is non-backtracking.

Then, two vertices of *T* are adjacent if one is a simple extension of another: the vertex (*r*, *v*_{1}, *v*_{2}, ..., *v*_{n}) is adjacent to the vertex (*r*, *v*_{1}, *v*_{2}, ..., *v*_{n-1}). Up to isomorphism, the same tree *T* is constructed regardless of the choice of the starting point *r*.

The covering map *f* maps the vertex (*r*) in *T* to the vertex *r* in *G*, and a vertex (*r*, *v*_{1}, *v*_{2}, ..., *v*_{n}) in *T* to the vertex *v*_{n} in *G*.

### Examples of universal coversEdit

The following figure illustrates the universal covering graph *T* of a graph *H*; the colours indicate the covering map.

For any *k*, all *k*-regular graphs have the same universal cover: the infinite *k*-regular tree.

## Topological crystalEdit

An infinite-fold abelian covering graph of a finite (multi)graph is called a topological crystal, an abstraction of crystal structures. For example, the diamond crystal as a graph is the maximal abelian covering graph of the four-edge dipole graph. This view combined with the idea of "standard realizations" turns out to be useful in a systematic design of (hypothetical) crystals.^{[1]}

## Planar coverEdit

A planar cover of a graph is a finite covering graph that is itself a planar graph. The property of having a planar cover may be characterized by forbidden minors, but the exact characterization of this form remains unknown. Every graph with an embedding in the projective plane has a planar cover coming from the orientable double cover of the projective plane; in 1988, Seiya Nagami conjectured that these are the only graphs with planar covers, but this remains unproven.^{[3]}

## Voltage graphsEdit

A common way to form covering graphs uses voltage graphs, in which the darts of the given graph *G* (that is, pairs of directed edges corresponding to the undirected edges of *G*) are labeled with inverse pairs of elements from some group. The derived graph of the voltage graph has as its vertices the pairs (*v*,*x*) where *v* is a vertex of *G* and *x* is a group element; a dart from *v* to *w* labeled with the group element *y* in *G* corresponds to an edge from (*v*,*x*) to (*w*,*xy*) in the derived graph.

The universal cover can be seen in this way as a derived graph of a voltage graph in which the edges of a spanning tree of the graph are labeled by the identity element of the group, and each remaining pair of darts is labeled by a distinct generating element of a free group. The bipartite double can be seen in this way as a derived graph of a voltage graph in which each dart is labeled by the nonzero element of the group of order two.

## NotesEdit

- ^
^{a}^{b}Sunada, Toshikazu (2012).*Topological Crystallography -With a View Towards Discrete Geometric Analysis-*. Springer. **^**Angluin 1980.**^**Hliněný, Petr (2010), "20 years of Negami's planar cover conjecture" (PDF),*Graphs and Combinatorics*,**26**(4): 525–536, CiteSeerX 10.1.1.605.4932, doi:10.1007/s00373-010-0934-9, MR 2669457.

## ReferencesEdit

- Chris Godsil and Gordon Royle:
*Algebraic Graph Theory*, Springer, 2004. Sect. 6.8. - Alon Amit, Nathan Linial, Jiří Matoušek, and Eyal Rozenman: "Random lifts of graphs",
*Proc. SODA 2001*, p. 883–894. - Dana Angluin: "Local and global properties in networks of processors",
*Proc. STOC 1980*, p. 82–93.