Graph Cover

A graph cover, also called a graph covering, of a graph G is a graph G^~ together with a graph projection p:G^~->G such that the restriction of p to the edges incident to each vertex v^~ of G^~ is a bijection onto the edges incident to p(v^~) in G (Gross and Tucker 1987). Equivalently, the neighborhood of every lifted vertex v^~ in the cover looks locally like the neighborhood of its image p(v^~) in the base graph, with incident edges corresponding one-to-one.

A vertex v^~ of G^~ with p(v^~)=v is called a lift of v.

A graph cover should not be confused with an edge cover, which is a set of edges whose endpoints contain all the vertices of a single graph.

A voltage graph gives a compact way to construct regular graph covers. A graph cover is a regular graph cover when its deck transformations act transitively on each fiber of the graph projection. Here "regular" refers to the covering action, not to a regular graph. More generally, permutation voltage assignments generate arbitrary graph covers (Gross and Tucker 1977).

See also

Cover, Deck Transformation, Edge Cover, Graph Isomorphism, Graph Projection, Regular Graph Cover, Voltage Graph

Explore with Wolfram|Alpha

References

Gross, J. L. and Tucker, T. W. "Generating All Graph Coverings by Permutation Voltage Assignments." Disc. Math. 18, 273-283, 1977.Gross, J. L. and Tucker, T. W. Topological Graph Theory. New York: Wiley, 1987.

Cite this as:

Weisstein, Eric W. "Graph Cover." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphCover.html

Subject classifications