Covering graph

Last updated August 14, 2023

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 combinatorial formulation of covering graphs is immediately generalized to the case of multigraphs. A covering graph is a special case of a covering complex.^[1] Both covering complexes and multigraphs with a 1-dimensional cell complex, are nothing but examples of covering spaces of topological spaces, so the terminology in the theory of covering spaces is available; say covering transformation group, universal covering, abelian covering, and maximal abelian covering.^[2]

Definition

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 fiberf⁻¹(v) has exactly h elements.

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 C is a 2-fold cover or a double cover of 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 × K₂:

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.^[3] 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₁, v₂, ..., 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₁, v₂, ..., v_n) is adjacent to the vertex (r, v₁, v₂, ..., 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₁, v₂, ..., v_n) in T to the vertex v_n 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 graphs have the same universal cover: the infinite k-regular tree.

Topological crystal

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.^[2]

Planar cover

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.^[4]

Voltage graphs

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.

Notes

↑ Rotman, Joseph (December 1973). "Covering complexes with applications to algebra". Rocky Mountain Journal of Mathematics. 3 (4): 641–674. doi: 10.1216/RMJ-1973-3-4-641 . ISSN 0035-7596 – via https://projecteuclid.org.{{cite journal}}: External link in |via= (help)
1 2 Sunada, Toshikazu (2012). "6 Topological Crystals". Topological Crystallography: With a View Towards Discrete Geometric Analysis. Springer. pp. 73–90. ISBN 978-4-431-54177-6.
↑ 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 .

Related Research Articles

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges.

In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph. Both problems are NP-complete.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, two graphs $and are homeomorphic if there is a graph isomorphism from some subdivision of to some subdivision of . If the edges of a graph are thought of as lines drawn from one vertex to another, then two graphs are homeomorphic to each other in the graph-theoretic sense precisely if they are homeomorphic in the topological sense.$

In graph theory, an undirected graph $H$ is called a minor of the graph $G$ if $H$ can be formed from $G$ by deleting edges, vertices and by contracting edges.

In the mathematical discipline of graph theory, the line graph of an undirected graph $G$ is another graph $L(G)$ that represents the adjacencies between edges of $G$ . $L(G)$ is constructed in the following way: for each edge in $G$ , make a vertex in $L(G)$ ; for every two edges in $G$ that have a vertex in common, make an edge between their corresponding vertices in $L(G)$ .

In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors. It was first studied in the 1970s in independent papers by Vizing and by Erdős, Rubin, and Taylor.

In the mathematical discipline of graph theory, the dual graph of a planar graph $G$ is a graph that has a vertex for each face of $G$ . The dual graph has an edge for each pair of faces in $G$ that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge $e$ of $G$ has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of $e$ . The definition of the dual depends on the choice of embedding of the graph $G$ , so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

In computer science, graph traversal refers to the process of visiting each vertex in a graph. Such traversals are classified by the order in which the vertices are visited. Tree traversal is a special case of graph traversal.

<span class="mw-page-title-main">Neighbourhood (graph theory)</span> Subgraph made of all nodes linked to a given node of a graph

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 subgraph of $G$ induced by all vertices adjacent to $v$ , i.e., the graph composed of the vertices adjacent to $v$ and all edges connecting vertices adjacent to $v$ .

In graph theory, 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 \times K 2$ . It is also called the Kronecker double cover, canonical double cover or simply the bipartite double of $G$ .

In graph theory, a Trémaux tree of an undirected graph $is a type of spanning tree, generalizing depth-first search trees. They are defined by the property that every edge of connects an ancestor-descendant pair in the tree. Trémaux trees are named after Charles Pierre Trémaux, a 19th-century French author who used a form of depth-first search as a strategy for solving mazes. They have also been called normal spanning trees, especially in the context of infinite graphs.$

In graph theory, a well-covered graph is an undirected graph in which every minimal vertex cover has the same size as every other minimal vertex cover. Equivalently, these are the graphs in which all maximal independent sets have equal size. Well-covered graphs were defined and first studied by Michael D. Plummer in 1970.

<span class="mw-page-title-main">Bipartite half</span> Graph whose nodes are one of the vertex sets of a bipartite graph

In graph theory, the bipartite half or half-square of a bipartite graph $G = (U, V, E)$ is a graph whose vertex set is one of the two sides of the bipartition (without loss of generality, $U$ ) and in which there is an edge $u i u j$ for each pair of vertices $u i, u j$ in $U$ that are at distance two from each other in $G$ . That is, in a more compact notation, the bipartite half is $G 2 [U]$ where the superscript 2 denotes the square of a graph and the square brackets denote an induced subgraph.

<span class="mw-page-title-main">Planar cover</span>

In graph theory, a planar cover of a finite graph G is a finite covering graph of G that is itself a planar graph. Every graph that can be embedded into the projective plane has a planar cover; an unsolved conjecture of Seiya Negami states that these are the only graphs with planar covers.

In geometry and crystallography, the Laves graph is an infinite and highly symmetric system of points and line segments in three-dimensional Euclidean space, forming a periodic graph. Three equal-length segments meet at 120° angles at each point, and all cycles use ten or more segments. It is the shortest possible triply periodic graph, relative to the volume of its fundamental domain. One arrangement of the Laves graph uses one out of every eight of the points in the integer lattice as its points, and connects all pairs of these points that are nearest neighbors, at distance $. It can also be defined, divorced from its geometry, as an abstract undirected graph, a covering graph of the complete graph on four vertices.$

In graph theory, a quotient graphQ of a graph G is a graph whose vertices are blocks of a partition of the vertices of G and where block B is adjacent to block C if some vertex in B is adjacent to some vertex in C with respect to the edge set of G. In other words, if G has edge set E and vertex set V and R is the equivalence relation induced by the partition, then the quotient graph has vertex set V/R and edge set {([u]_R, [v]_R) | (u, v) ∈ E(G)}.

In graph theory, a branch of mathematics, a map graph is an undirected graph formed as the intersection graph of finitely many simply connected and internally disjoint regions of the Euclidean plane. The map graphs include the planar graphs, but are more general. Any number of regions can meet at a common corner, and when they do the map graph will contain a clique connecting the corresponding vertices, unlike planar graphs in which the largest cliques have only four vertices. Another example of a map graph is the king's graph, a map graph of the squares of the chessboard connecting pairs of squares between which the chess king can move.

In topological graph theory, a graph-encoded map or gem is a method of encoding a cellular embedding of a graph using a different graph with four vertices per edge of the original graph. It is the topological analogue of runcination, a geometric operation on polyhedra. Graph-encoded maps were formulated and named by Lins (1982). Alternative and equivalent systems for representing cellular embeddings include signed rotation systems and ribbon graphs.

References

Godsil, Chris; Royle, Gordon F. (2001). "§6.8 Foldings and Covers". Algebraic Graph Theory. Graduate Texts in Mathematics. Vol. 207. Springer. pp. 114–6. ISBN 978-0-387-95220-8.
Amit, Alon; Linial, Nathan; Matoušek, Jiří; Rozenman, Eyal (2001). "Random lifts of graphs". Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms (SODA '01). Society for Industrial and Applied Mathematics. pp. 883–894. CiteSeerX 10.1.1.719.3508 . ISBN 978-0-89871-490-6.
Angluin, Dana (1980). "Local and global properties in networks of processors (Extended Abstract)". Proceedings of the twelfth annual ACM symposium on Theory of computing (STOC '80). Association for Computing Machinery. pp. 82–93. doi:10.1145/800141.804655. ISBN 978-0-89791-017-0.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Rotman, Joseph (December 1973). "Covering complexes with applications to algebra". Rocky Mountain Journal of Mathematics. 3 (4): 641–674. doi: 10.1216/RMJ-1973-3-4-641 . ISSN 0035-7596 – via https://projecteuclid.org.{{cite journal}}: External link in |via= (help)

[sunada-2] 1 2 Sunada, Toshikazu (2012). "6 Topological Crystals". Topological Crystallography: With a View Towards Discrete Geometric Analysis. Springer. pp. 73–90. ISBN 978-4-431-54177-6.

[3] Angluin 1980

[4] 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 .

[1]

[2]

[3]

[4]