Covering Graph - Universal 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 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.

Read more about this topic:  Covering Graph

Famous quotes containing the words universal and/or cover:

    The world still wants its poet-priest, a reconciler, who shall not trifle with Shakspeare the player, nor shall grope in graves with Swedenborg the mourner; but who shall see, speak, and act, with equal inspiration. For knowledge will brighten the sunshine; right is more beautiful than private affection; and love is compatible with universal wisdom.
    Ralph Waldo Emerson (1803–1882)

    I wouldn’t pray just for a old man that’s dead because he’s all right. If I was to pray, I’d pray for the folks that’s alive and don’t know which way to turn. Grampa here, he ain’t got no more trouble like that. He’s got his job all cut out for him. So cover him up and let him get to it.
    Nunnally Johnson (1897–1977)