Covering graph
Encyclopedia
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.
Note that a covering in graph theory may also refer to an unrelated concept, a subset of vertices that touches all edges.
of v is a bijection onto the neighbourhood of f(v) ∈ 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.
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:
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 × K2:
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.
.
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, v1, v2, ..., vn) of vertices of G such that
Then, two vertices of T are adjacent if one is a simple extension of another: the vertex (r, v1, v2, ..., vn) is adjacent to the vertex (r, v1, v2, ..., vn-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, v1, v2, ..., vn) in T to the vertex vn in G.
For any k, all k-regular graph
s have the same universal cover: the infinite k-regular tree.
s, 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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
discipline of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
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
Neighbourhood (graph theory)
In graph theory, an adjacent vertex of a vertex v in a graph is a vertex that is connected to v by an edge. The neighbourhood of a vertex v in a graph G is the induced subgraph of G consisting of all vertices adjacent to v and all edges connecting two such vertices. For example, the image shows a...
of a v vertex in C is mapped bijectively
Bijection
A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
onto the neighbourhood of f(v) in G.
Note that a covering in graph theory may also refer to an unrelated concept, a subset of vertices that touches all edges.
Definition
Let G = (V, E) and C = (V2, E2) be two graphs, and let f: V2 → V be a surjection. Then f is a covering map from C to G if for each v ∈ V2, the restriction of f to the neighbourhoodNeighbourhood (graph theory)
In graph theory, an adjacent vertex of a vertex v in a graph is a vertex that is connected to v by an edge. The neighbourhood of a vertex v in a graph G is the induced subgraph of G consisting of all vertices adjacent to v and all edges connecting two such vertices. For example, the image shows a...
of v is a bijection onto the neighbourhood of f(v) ∈ 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.
Examples
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 cover
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
Bipartite double cover
In graph theoretic mathematics, the bipartite double cover of an undirected graph G is a bipartite covering graph of G, with twice as many vertices as G. It can be constructed as the tensor product of graphs G × K2...
of G, which is a bipartite graph
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
and a double cover of G. The bipartite double cover of G is the tensor product of graphs
Tensor product of graphs
In graph theory, the tensor product G × H of graphs G and H is a graph such that* the vertex set of G × H is the Cartesian product V × V; and...
G × K2:
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 cover
For any connected graph G, it is possible to construct its universal covering graph. 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 treeTree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles 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, v1, v2, ..., vn) of vertices of G such that
- vi and vi+1 are adjacent in G for all i, i.e., w is a walk
- vi-1 ≠ vi+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, v1, v2, ..., vn) is adjacent to the vertex (r, v1, v2, ..., vn-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, v1, v2, ..., vn) in T to the vertex vn in G.
Examples of universal covers
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 graph
Regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
s have the same universal cover: the infinite k-regular tree.
Voltage graphs
A common way to form covering graphs uses voltage graphVoltage graph
In graph-theoretic mathematics, a voltage graph is a directed graph whose edges are labelled invertibly by elements of a group. It is formally identical to a gain graph, but it is generally used in topological graph theory as a concise way to specify another graph called the derived graph of the...
s, 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
Group (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
. 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
Spanning tree
Spanning tree can refer to:* Spanning tree , a tree which contains every vertex of a more general graph* Spanning tree protocol, a protocol for finding spanning trees in bridged networks...
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
Free group
In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses...
. 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.