Covering graph

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 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.

Contents

Definition

Let G = (V, E) and C = (V2, E2) be two graphs, and let f: V2V be a surjection. Then f is a covering map from C to G if for each vV2, the restriction of f to the neighbourhood 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.

Covering-graph-4.svg

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:

Covering-graph-4-a.svg

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:

Covering-graph-4-b.svg

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 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:

Covering-graph-2.svg

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.[1] 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-1vi+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.

Covering-graph-5.svg

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

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

  1. ^ Angluin 1980.

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Covering (graph theory) — In the mathematical discipline of graph theory, a covering (or cover) of a graph is a set of vertices (or edges) such that each edge (vertex) of the graph touches (is incident with) at least one element of the set.It is of mathematical interest… …   Wikipedia

  • Covering — may refer to: Mathematics In topology: Covering map, a function from one space to another with uniform local neighborhoods Cover (topology), a system of (usually, open or closed) sets whose union is a given topological space Lebesgue covering… …   Wikipedia

  • Covering space — A covering map satisfies the local triviality condition. Intuitively, such maps locally project a stack of pancakes above an open region, U, onto U. In mathematics, more specifically algebraic topology, a covering map is a continuous surjective… …   Wikipedia

  • 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 …   Wikipedia

  • Graph property — In graph theory a graph property is any inherently graph theoretical property of graphs (formal definitions follow), distinguished from properties of graphs described in terms of various graph representations: graph drawings, data structures for… …   Wikipedia

  • Graph of groups — In geometric group theory, a graph of groups is an object consisting of a collection of groups indexed by the vertices and edges of a graph, together with a family of injective homomorphisms of the edge groups into the vertex groups.There is a… …   Wikipedia

  • Graph factorization — Not to be confused with Factor graph. 1 factorization of Desargues graph: each color class is a 1 factor …   Wikipedia

  • Covering problem — In combinatorics and computer science, covering problems are computational problems that ask whether a certain combinatorial structure covers another, or how large the structure has to be to do that. Covering problems are minimization problems… …   Wikipedia

  • Covering relation — For other uses of Cover in mathematics, see Cover (mathematics). The Hasse diagram of the power set of three elements, partially ordered by inclusion. In mathematics, especially order theory, the covering relation of a partially ordered set is… …   Wikipedia

  • covering number — noun The number of vertices in a minimum vertex cover of a graph, often denoted as . See Also: edge covering number …   Wiktionary

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”