In the mathematical discipline of graph theory, a graphC 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 in G.
The term lift is often used as a synonym for a covering graph of a connected graph.
Though it may be misleading, there is no (obvious) relationship between covering graph and vertex cover or edge cover.
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 = (V1, E1) and C = (V2, E2) be two graphs, and let f: V2 → V1 be a surjection. Then f is a covering map from C to G if for each v ∈ V2, 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−1(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.
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, 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 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]
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.
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 a 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.
The Hamiltonian path problem is a topic discussed in the fields of complexity theory and graph theory. It decides if a directed or undirected graph, G, contains a Hamiltonian path, a path that visits every vertex in the graph exactly once. The problem may specify the start and end of the path, in which case the starting vertex s and ending vertex t must be identified.
In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal.
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 their diagrams 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 field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.
In the mathematical field of graph theory, an automorphism is a permutation of the vertices such that edges are mapped to edges and non-edges are mapped to non-edges. A graph is a vertex-transitive graph if, given any two vertices v1 and v2 of G, there is an automorphism f such that
In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct. A directed path in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction.
In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices. Proved by Karl Menger in 1927, it characterizes the connectivity of a graph. It is generalized by the max-flow min-cut theorem, which is a weighted, edge version, and which in turn is a special case of the strong duality theorem for linear programs.
The five color theorem is a result from graph theory that given a plane separated into regions, such as a political map of the countries of the world, the regions may be colored using no more than five colors in such a way that no two adjacent regions receive the same color.
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.
Bass–Serre theory is a part of the mathematical subject of group theory that deals with analyzing the algebraic structure of groups acting by automorphisms on simplicial trees. The theory relates group actions on trees with decomposing groups as iterated applications of the operations of free product with amalgamation and HNN extension, via the notion of the fundamental group of a graph of groups. Bass–Serre theory can be regarded as one-dimensional version of the orbifold theory.
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 × K2. It is also called the Kronecker double cover, canonical double cover or simply the bipartite double of G.
In graph theory, a well-covered graph is an undirected graph in which the minimal vertex covers all have the same size. Here, a vertex cover is a set of vertices that touches all edges, and it is minimal if removing any vertex from it would leave some edge uncovered. Equivalently, well-covered graphs 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.
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 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.
In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph.
In the mathematical field of graph theory, Hall-type theorems for hypergraphs are several generalizations of Hall's marriage theorem from graphs to hypergraphs. Such theorems were proved by Ofra Kessler, Ron Aharoni, Penny Haxell, Roy Meshulam, and others.
In graph theory, a balanced hypergraph is a hypergraph that has several properties analogous to that of a bipartite graph.
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. ISBN978-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.
