Voltage graph

A voltage graph is a graph whose edges are labelled invertibly by elements of a group. It is formally identical to a gain graph, but it is generally used as a concise way to specify another graph called the "derived graph" of the voltage graph.

Formal definition

Formal definition of a $mathbb\{Z\}\_\{n\}$-voltage graph:
* Begin with a digraph "G". (The direction is solely for convenience in notation.)
* A $mathbb\{Z\}\_\{n\}$-voltage on an arc of $G$ is a label of the arc by a number $i\; (\; ext\{mod\; \}n).$
* A $mathbb\{Z\}\_\{n\}$-voltage assignment is a function $alpha\; :\; E(G)\; ightarrow\; mathbb\{Z\}\_\{n\}$ that labels each arc of $G$ with a $mathbb\{Z\}\_\{n\}$-voltage.
* A $mathbb\{Z\}\_\{n\}$-voltage graph (or cyclic-voltage graph) is a pair $(\; G,\; alpha:\; E(G)\; ightarrow\; mathbb\{Z\}\_\{n\}\; )$ such that $G$ is a digraph and $alpha$ is a voltage assignment.
* The voltage group of a voltage graph $(\; G,\; alpha:\; E(G)\; ightarrow\; mathbb\{Z\}\_\{n\}\; )$ is the group $mathbb\{Z\}\_\{n\}$ from which the voltages are assigned.

A voltage graph may have any group as its voltage group, but the groups $mathbb\{Z\}\_\{n\}$ are usually the most useful.

Note that the voltages of a voltage graph need not satisfy Kirkhhoff's voltage law, that the sum of voltages around a closed path is 0. Thus, the name may be somewhat misleading. It results from the origin of voltage graphs as dual to the current graphs of topological graph theory.

The derived graph

The derived graph of a voltage graph $(\; G,\; alpha:\; E(G)\; ightarrow\; mathbb\{Z\}\_\{n\}\; )$ is the graph $ilde\; G$ whose vertex set is $ilde\; V\; =\; V\; imes\; mathbb\{Z\}\_\{n\}$ and whose edge set is $ilde\; E\; =\; E\; imes\; mathbb\{Z\}\_\{n\}$, where the endpoints of an edge ("e", "k") such that "e" has tail "v" and head "w" are $(v,\; k)$ and $(w,\; k+alpha(e))$.

References

* J.L. Gross (1974), Voltage graphs. "Discrete Mathematics", Vol. 9, pp. 239-246.
* J.L. Gross and T.W. Tucker (1977), Generating all graph coverings by permutation voltage assignments. "Discrete Mathematics", Vol. 18, pp. 273-283.
* J.L. Gross and T.W. Tucker (1987), "Topological Graph Theory". Wiley, New York.