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:

    Vanity, or to call it by a gentler name, the desire of admiration and applause, is, perhaps, the most universal principle of human actions.... Where that desire is wanting, we are apt to be indifferent, listless, indolent, and inert.... I will own to you, under the secrecy of confession, that my vanity has very often made me take great pains to make many a woman in love with me, if I could, for whose person I would not have given a pinch of snuff.
    Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)

    There is nothing more poetic and terrible than the skyscrapers’ battle with the heavens that cover them. Snow, rain, and mist highlight, drench, or conceal the vast towers, but those towers, hostile to mystery and blind to any sort of play, shear off the rain’s tresses and shine their three thousand swords through the soft swan of the fog.
    Federico García Lorca (1898–1936)