Gain graph
From Wikipedia, the free encyclopedia
A gain graph is a graph whose edges are labelled invertibly, or orientably, by elements of a group G. This means that, if an edge e in one direction has label g (a group element), 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 and the value φ(e) is the gain of e (in some indicated direction).
A gain should not be confused with a weight on an edge, whose value is independent of the orientation of the edge.
Gain graphs used in topological graph theory are known as voltage graphs. The term "gain graph" is more usual in 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 (and much of the theory of biased graphs is a generalization of that of gain graphs), the reader should refer to the article on biased graphs for more information and examples.
