A gaingraph is a graph whose edges are labelled "invertibly", or "orientably", by elements of a groupG. This means that, if an edge e in one direction has labelg, then in the other direction it has label g −1. The label function φ therefore has the property that it is defined differently, but not independently, on the two different orientations, or directions, of an edge e. The group G is called the gain group, φ is the gain function, and the value φ is the gain of e. A gain graph is a generalization of a signed graph, where the gain group G has only two elements. SeeZaslavsky. A gain should not be confused with a weight on an edge, whose value is independent of the orientation of the edge.
Suppose we have some hyperplanes in R n given by equations of the form xj = g xi. The geometry of the hyperplanes can be treated by using the following gain graph: The vertex set is. There is an edge ij with gain g for each hyperplane with equation xj = g xi. These hyperplanes are treated through the frame matroid of the gain graph.
Or, suppose we have hyperplanes given by equations of the form xj = xi + g. The geometry of these hyperplanes can be treated by using the gain graph with the same vertex set and an edge ij with gain g for each hyperplane with equation xj = xi + g. These hyperplanes are studied via the lift matroid of the gain graph.
Suppose the gain group has an action on a set Q. Assigning an element si of Q to each vertex gives a state of the gain graph. An edge is satisfied if, for each edge ij with gain g, the equation sj = si g is satisfied; otherwise it is frustrated. A state is satisfied if every edge is satisfied. In physics this corresponds to a ground state, 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 in topological graph theory as a means to construct graph embeddings in surfaces are known as "voltage graphs". The term "gain graph" is more usual in other contexts, e.g., biased graph theory and matroid theory. The term group-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, the reader should refer to the article on biased graphs for more information and examples.
