Again graph is agraph whose edges are labelled "invertibly", or "orientably", by elements of agroupG. This means that, if an edgee in one direction has labelg (a group element), then in the other direction it has labelg ⁻¹. The label functionφ therefore has the property that it is defined differently, but not independently, on the two different orientations, or directions, of an edgee. The groupG is called thegain group,φ is thegain function, and the valueφ(e) is thegain ofe (in some indicated direction). A gain graph is a generalization of asigned graph, where the gain groupG has only two elements. See Zaslavsky (1989, 1991).

A gain should not be confused with aweight on an edge, whose value is independent of the orientation of the edge.

Some reasons to be interested in gain graphs are their connections tonetwork flow theory incombinatorial optimization, togeometry, and tophysics.

• The mathematics of anetwork with gains, orgeneralized network, is connected with theframe matroid of the gain graph.
• Suppose we have somehyperplanes inR ⁿ given by equations of the formx_j =g x_i . The geometry of the hyperplanes can be treated by using the following gain graph: The vertex set is {1,2,...,n}. There is an edgeij with gaing (in the direction fromi toj) for each hyperplane with equationx_j = g x_i . These hyperplanes are treated through the frame matroid of the gain graph (Zaslavsky 2003).
• Or, suppose we have hyperplanes given by equations of the formx_j =x_i +g. The geometry of these hyperplanes can be treated by using the gain graph with the same vertex set and an edgeij with gaing (in the direction fromi toj) for each hyperplane with equationx_j =x_i +g. These hyperplanes are studied via thelift matroid of the gain graph (Zaslavsky 2003).
• Suppose the gain group has anaction on a setQ. Assigning an elements_i ofQ to each vertex gives astate of the gain graph. An edge issatisfied if, for each edgeij with gaing (in the direction fromi toj), the equations_j =s_i g is satisfied; otherwise it isfrustrated. A state issatisfied if every edge is satisfied. In physics this corresponds to aground state (a state of lowest energy), if such a state exists. An important problem in physics, especially in the theory ofspin glasses, is to determine a state with the fewest frustrated edges.

Gain graphs used intopological graph theory as a means to constructgraph embeddings in surfaces are known as "voltage graphs" (Gross 1974; Gross and Tucker 1977). The term "gain graph" is more usual in other contexts, e.g.,biased graph theory andmatroid theory. The termgroup-labelled graph has also been used, but it is ambiguous since "group labels" may be—and have been—treated as weights.

Since much of the theory of gain graphs is a special case of that of biased graphs (and much of the theory of biased graphs is a generalization of that of gain graphs), the reader should refer to the article onbiased graphs for more information and examples.

• Jonathan 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.
• Thomas Zaslavsky (1989), Biased graphs. I. Bias, balance, and gains.Journal of Combinatorial Theory, Series B, Vol. 47, 32–52.
• Thomas Zaslavsky (1991), Biased graphs. II. The three matroids.Journal of Combinatorial Theory, Series B, Vol. 51, 46–72.
• Thomas Zaslavsky (1999). A mathematical bibliography of signed and gain graphs and allied areas.Electronic Journal of Combinatorics, Dynamic Surveys in Combinatorics, #DS8.
• Thomas Zaslavsky (2003), Biased graphs IV: Geometrical realizations.Journal of Combinatorial Theory, Series B, Vol. 89, no. 2, pp. 231–297.

• Matroid theory
• Extensions and generalizations of graphs

• Articles with short description
• Short description is different from Wikidata