In the
mathematical
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
discipline of
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
is a covering graph of another graph if there is a covering map from the
vertex
Vertex, vertices or vertexes may refer to:
Science and technology Mathematics and computer science
*Vertex (geometry), a point where two or more curves, lines, or edges meet
*Vertex (computer graphics), a data structure that describes the position ...
set of to the vertex set of . A covering map is a
surjection
In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of i ...
and a local
isomorphism
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
: the
neighbourhood
A neighbourhood (British English, Irish English, Australian English and Canadian English) or neighborhood (American English; see spelling differences) is a geographically localised community within a larger city, town, suburb or rural are ...
of a vertex in is mapped
bijectively onto the neighbourhood of in .
The term lift is often used as a synonym for a covering graph of a
connected graph
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgrap ...
.
Though it may be misleading, there is no (obvious) relationship between covering graph and
vertex cover
In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph.
In computer science, the problem of finding a minimum vertex cover is a classical optimizat ...
or
edge cover
In graph theory, an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set.
In computer science, the minimum edge cover problem is the problem of finding an edge cover of minimum size ...
.
The
combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
formulation of covering graphs is immediately generalized to the case of
multigraph
In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by more ...
s. In the case of a multigraph with a 1-dimensional cell complex, a covering graph is nothing but a special example of
covering space A covering of a topological space X is a continuous map \pi : E \rightarrow X with special properties.
Definition
Let X be a topological space. A covering of X is a continuous map
: \pi : E \rightarrow X
such that there exists a discrete spa ...
s of
topological space
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called points ...
s, so the terminology in the theory of covering spaces is available; say covering transformation group, universal covering, abelian covering, and maximal abelian covering.
Definition
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
In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of i ...
. Then ''f'' is a ''covering map'' from ''C'' to ''G'' if for each ''v'' ∈ ''V''
2, the restriction of ''f'' to the
neighbourhood
A neighbourhood (British English, Irish English, Australian English and Canadian English) or neighborhood (American English; see spelling differences) is a geographically localised community within a larger city, town, suburb or rural are ...
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.
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 is a bijection onto . 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
In graph theory, the bipartite double cover of an undirected graph is a bipartite, covering graph of , with twice as many vertices as . It can be constructed as the tensor product of graphs, . It is also called the Kronecker double cover, cano ...
of ''G'', which is a
bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
and a double cover of ''G''. The bipartite double cover of ''G'' is the
tensor product of graphs
In graph theory, the tensor product of graphs and is a graph such that
* the vertex set of is the Cartesian product ; and
* vertices and are adjacent in if and only if
** is adjacent to in , and
** is adjacent to in .
The tensor prod ...
''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 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 A covering of a topological space X is a continuous map \pi : E \rightarrow X with special properties.
Definition
Let X be a topological space. A covering of X is a continuous map
: \pi : E \rightarrow X
such that there exists a discrete spa ...
concept from topology; the topological requirement that a universal cover be
simply connected
In topology, a topological space is called simply connected (or 1-connected, or 1-simply connected) if it is path-connected and every path between two points can be continuously transformed (intuitively for embedded spaces, staying within the spac ...
translates in graph-theoretic terms to a requirement that it be acyclic and connected; that is, a
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
.
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 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
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 o ...
s 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
In graph theory, a dipole graph, dipole, bond graph, or linkage, is a multigraph consisting of two vertices connected with a number of parallel edges. A dipole graph containing edges is called the dipole graph, and is denoted by . The dipole ...
. This view combined with the idea of "standard realizations" turns out to be useful in a systematic design of (hypothetical) crystals.
Planar cover
A
planar cover
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 state ...
of a graph is a finite covering graph that is itself a
planar graph
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 ...
. 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 mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup.
When some object X is said to be embedded in another object Y, the embedding is gi ...
in the
projective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines (namely, parallel lines) that do ...
has a planar cover coming from the
orientable double cover
In mathematics, orientability is a property of some topological spaces such as real vector spaces, Euclidean spaces, Surface (topology), surfaces, and more generally manifolds that allows a consistent definition of "clockwise" and "counterclo ...
of the projective plane; in 1988, Seiya Nagami conjectured that these are the only graphs with planar covers, but this remains unproven.
[.]
Voltage graphs
A common way to form covering graphs uses
voltage graph
In graph theory, 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 gra ...
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
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
. 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
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
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
In mathematics, the free group ''F'S'' over a given set ''S'' consists of all words that can be built from members of ''S'', considering two words to be different unless their equality follows from the group axioms (e.g. ''st'' = ''suu''−1' ...
. 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
References
*
*
* {{cite book , first=Dana , last=Angluin , chapter=Local and global properties in networks of processors (Extended Abstract) , title=Proceedings of the twelfth annual ACM symposium on Theory of computing (STOC '80) , publisher=Association for Computing Machinery , year=1980 , isbn=978-0-89791-017-0 , pages=82–93 , doi=10.1145/800141.804655
Graph theory