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-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.
Read more about this topic: Covering Graph
Famous quotes containing the words universal and/or cover:
“The universal soul is the alone creator of the useful and the beautiful; therefore to make anything useful or beautiful, the individual must be submitted to the universal mind.”
—Ralph Waldo Emerson (18031882)
“Now folks, I hereby declare the first church of Tombstone, which aint got no name yet or no preacher either, officially dedicated. Now I dont pretend to be no preacher, but Ive read the Good Book from cover to cover and back again, and I nary found one word agin dancin. So well commence by havin a dad blasted good dance.”
—Samuel G. Engel (19041984)