A Mathematical Bibliography of Signed and Gain Graphs and Allied Areas

Thomas Zaslavsky


A signed graph is a graph whose edges are labeled by signs. This is a bibliography of signed graphs and related mathematics.

Several kinds of labelled graph have been called "signed" yet are mathematically very different. I distinguish four types:

  • Group-signed graphs: the edge labels are elements of a 2-element group and are multiplied around a polygon (or along any walk). Among the natural generalizations are larger groups and vertex signs.
  • Sign-colored graphs, in which the edges are labelled from a two-element set that is acted upon by the sign group: - interchanges labels, + leaves them unchanged. This is the kind of "signed graph" found in knot theory. The natural generalization is to more colors and more general groups — or no group.
  • Weighted graphs, in which the edge labels are the elements +1 and -1 of the integers or another additive domain. Weights behave like numbers, not signs; thus I regard work on weighted graphs as outside the scope of the bibliography — except (to some extent) when the author calls the weights "signs".
  • Labelled graphs where the labels have no structure or properties but are called "signs" for any or no reason.


Full Text: PDF