Voltage graph

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

A voltage graph is a directed graph whose edges are labeled by elements of a group (and the labels are invertible). It is a concise way to specify another graph called the derived graph.

Common choices for the labeling group:
- Z2 (the two-element group): used to build the bipartite double cover of a graph.
- Free groups: used for the universal cover.
- Z^d: the d-dimensional integer lattice, used for describing periodic structures in d-dimensional space.
- Zn (finite cyclic groups) for n > 2.

If the group is cyclic, the voltage graph is often called a cyclic-voltage graph.

How the derived graph works:
- Given a voltage graph (G, α) with α mapping each edge to a group element, its derived graph G~ has vertices V×G and edges E×G.
- An edge e from vertex v to w labeled by α(e) connects (v, g) to (w, g·α(e)) for each group element g.
- If you want to treat the base graph as undirected, replace each edge by a pair of oppositely directed edges labeled by inverse group elements. The derived graph then also looks like an undirected graph.

The derived graph has a nice property: it is a covering graph of the original voltage graph. If no edge has the identity label, the vertices of the derived graph can be colored by the group elements, using as many colors as the group order.

Special cases and applications:
- Bipartite double cover: when every edge is labeled with the non-identity element of Z2, the derived graph is bipartite.
- There are polynomial-time algorithms to determine if a Z^d-voltage graph’s derived graph contains directed cycles.
- Any Cayley graph of a group G with a generator set can be seen as the derived graph of a voltage graph with one vertex and loops labeled by the generators.

Examples:
- Petersen graph: the derived graph of a Z5-voltage graph arranged as a dumbbell with two vertices and three edges (one edge between the two vertices and a loop at each vertex). One loop is labeled 1, the other 2, and the interconnecting edge is labeled 0.
- Generalized Petersen graphs GP(n,k) can be constructed similarly from the same base dumbbell graph with labels 1, 0, and k in Z_n.
- Periodic tilings of the plane: their vertices and edges can be obtained as derived graphs from a finite graph with voltages in Z^2.