Voltage graph

From Wikipedia, the free encyclopedia

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.

[edit] 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\ (\text{mod }n).
  • A \mathbb{Z}_{n}-voltage assignment is a function \alpha : E(G) \rightarrow \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) \rightarrow \mathbb{Z}_{n} ) such that G is a digraph and α is a voltage assignment.
  • The voltage group of a voltage graph ( G, \alpha: E(G) \rightarrow \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.

[edit] The derived graph

The derived graph of a voltage graph ( G, \alpha: E(G) \rightarrow \mathbb{Z}_{n} ) is the graph \tilde G whose vertex set is \tilde V = V \times \mathbb{Z}_{n} and whose edge set is \tilde E = E \times \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)).

[edit] 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.