Voltage Graph

A voltage graph is a graph together with an assignment of elements of a group , called the voltage group, to the oriented edges of the graph. More precisely, if each edge of a graph is replaced by two oppositely oriented darts and , a voltage assignment is a function from the darts to such that

(1)

A voltage assignment may be specified by choosing one orientation of each edge and assigning that dart a voltage. The inverse rule then determines the voltage on the oppositely oriented dart. When a small base graph is used explicitly, a chosen dart from vertex to vertex with voltage is often recorded as a voltage triple .

The voltage assignment determines a derived graph whose vertex set is . For an oriented edge of with voltage and for each , the derived graph has an edge

(2)

Thus the product of voltages along a walk in the base graph records how the lifted walk moves among the sheets of the cover. The natural projection that sends to gives a covering graph projection. The voltage group acts on by left multiplication on the second coordinate, giving a semiregular group action whose orbits are the fibers of the projection, that is, the sets of vertices mapping to single vertices of .

In this context, a graph cover of means a graph together with a graph projection such that, at each vertex of , the edges incident to are mapped bijectively onto the edges incident to . Thus, locally around each lifted vertex, the cover looks exactly like the base graph.

For example, the Petersen graph is the derived graph of a voltage graph whose voltage group is the cyclic group , which arises from the inherent symmetry of the graph. To recover a voltage presentation from a given graph, examine the structure of its automorphism group to identify subgroups whose action on the vertices is a semiregular group action. When the desired presentation has a cyclic group as its voltage group, the relevant subgroups are cyclic. In the conventional Petersen graph embedding, rotation by generates such a subgroup, which is isomorphic to . Since no nonidentity rotation fixes a vertex, this subgroup acts semiregularly on the vertices and is used as the voltage group. The group orbits of the subgroup are the five outer-cycle vertices and the five inner-star vertices. The corresponding base graph has one vertex for each group orbit, denoted and , respectively.

The voltage in each triple records how far the lifted edge shifts the second coordinate in . In this embedding, an outer edge has shift 1, a spoke has shift 0, and an inner-star edge has shift 2. With these choices, one convenient set of voltage triples is

(3)

Using the base-graph vertex labels 1 and 2 for and , respectively, gives the numeric voltage triples

(4)

where the third entry in each triple is interpreted as a residue modulo 5. Writing subscripts modulo 5, the derived graph has vertices and and edges

(5)

These three edge types are the outer 5-cycle, the five spokes, and the inner pentagram in this embedding.

It is useful to distinguish the existence of a voltage presentation from the appearance of a particular graph embedding. A circulant graph drawn with vertices 0, 1, ..., around a circle so that rotation by one step preserves adjacency gives a voltage presentation with a cyclic voltage group and a base graph having a single vertex. In contrast, an LCF notation embedding is voltage only when the repeated LCF pattern is realized by a genuine cyclic graph automorphism; the existence of a Hamiltonian cycle displayed on a circle does not by itself imply a semiregular group action. Conversely, a voltage embedding need not be an LCF or circular embedding. The term voltage in this sense records a cyclic graph automorphism and quotient voltage data, not necessarily the radial-looking geometry of a particular drawing.

For example, the Paley graph of order 13 is a circulant graph on the cyclic group , so a semiregular action by a cyclic group has a single group orbit and the corresponding radial voltage drawing naturally places the vertices on one circle. The Paley graph of order 25 is built from the finite field , whose additive group is isomorphic to rather than . Cyclic actions of order 5 therefore have five vertex orbits, and the corresponding voltage drawing organizes fibers over multiple base graph vertices. Thus identifying an embedding as voltage points to an underlying semiregular group action and quotient presentation, while LCF and circulant descriptions record Hamiltonian-cycle notation and cyclic adjacency structure, respectively.

Ordinary voltage assignments provide a compact way to describe regular graph covers. More generally, permutation voltage assignments generate arbitrary graph covers (Gross and Tucker 1977). Voltage graphs are especially useful in topological graph theory, where they encode graph covers and derived embeddings on surfaces (Gross 1974, Gross and Tucker 1987).