Gain graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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, φ is the gain function, and the value φ(e) is the gain of e (in some indicated direction). A gain graph is a generalization of a signed graph, where the gain group G has only two elements. See Zaslavsky (1989, 1991).

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

Applications[edit]

Some reasons to be interested in gain graphs are their connections to network flow theory in combinatorial optimization, to geometry, and to physics.

  • The mathematics of a network with gains, or generalized network, is connected with the frame matroid of the gain graph.
  • Suppose we have some hyperplanes in 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 {1,2,...,n}. There is an edge ij with gain g (in the direction from i to j) for each hyperplane with equation xj = g xi . These hyperplanes are treated through the frame matroid of the gain graph (Zaslavsky 2003).
  • 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 (in the direction from i to j) for each hyperplane with equation xj = xi + g. These hyperplanes are studied via the lift matroid of the gain graph (Zaslavsky 2003).
  • 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 (in the direction from i to j), 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 (a state of lowest energy), if such a state exists. An important problem in physics, especially in the theory of spin glasses, is to determine a state with the fewest frustrated edges.

Related concepts[edit]

Gain graphs used in topological graph theory as a means to construct graph 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 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.

References[edit]

  • 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.