Voltage graph

In graph theory, a voltage graph is a directed graph whose edges are labelled invertibly by elements of a group. It is formally identical to a gain graph, but it is generally used in topological graph theory as a concise way to specify another graph called the derived graph of the voltage graph. In graph theory, a voltage graph is a directed graph whose edges are labelled invertibly by elements of a group. It is formally identical to a gain graph, but it is generally used in topological graph theory as a concise way to specify another graph called the derived graph of the voltage graph. Typical choices of the groups used for voltage graphs include the two-element group ℤ2 (for defining the bipartite double cover of a graph), free groups (for defining the universal cover of a graph), d-dimensional integer lattices ℤd (viewed as a group under vector addition, for defining periodic structures in d-dimensional Euclidean space), and finite cyclic groups ℤn for n > 2. When Π is a cyclic group, the voltage graph may be called a cyclic-voltage graph. Formal definition of a Π-voltage graph, for a given group Π: Note that the voltages of a voltage graph need not satisfy Kirchhoff's voltage law, that the sum of voltages around a closed path is 0 (the identity element of the group), although this law does hold for the derived graphs described below. 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 of a voltage graph ( G , α : E ( G ) → Z n ) {displaystyle (G,alpha :E(G) ightarrow mathbb {Z} _{n})} is the graph G ~ {displaystyle { ilde {G}}} whose vertex set is V ~ = V × Z n {displaystyle { ilde {V}}=V imes mathbb {Z} _{n}} and whose edge set is E ~ = E × Z n {displaystyle { 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 ) {displaystyle (v, k)} and ( w ,   k + α ( e ) ) {displaystyle (w, k+alpha (e))} . Although voltage graphs are defined for digraphs, they may be extended to undirected graphs by replacing each undirected edge by a pair of oppositely ordered directed edges and by requiring that these edges have labels that are inverse to each other in the group structure. In this case, the derived graph will also have the property that its directed edges form pairs of oppositely oriented edges, so the derived graph may itself be interpreted as being an undirected graph. The derived graph is a covering graph of the given voltage graph. If no edge label of the voltage graph is the identity element, then the group elements associated with the vertices of the derived graph provide a coloring of the derived graph with a number of colors equal to the group order. An important special case is the bipartite double cover, the derived graph of a voltage graph in which all edges are labeled with the non-identity element of a two-element group. Because the order of the group is two, the derived graph in this case is guaranteed to be bipartite. Polynomial time algorithms are known for determining whether the derived graph of a Z d {displaystyle mathbb {Z} ^{d}} -voltage graph contains any directed cycles. Any Cayley graph of a group Π, with a given set Γ of generators, may be defined as the derived graph for a Π-voltage graph having one vertex and |Γ| self-loops, each labeled with one of the generators in Γ.