signed graph

A signed graph is an undirected simple graph (a set VV of vertices together with a collection EE of two-element subsets of VV called edges) plus a function from EE to a two-element set of “signs”, e.g., σ:E{+,}\sigma: E \to \{+, -\}. A morphism of signed graphs is a function between vertex sets which preserves signed graph structure.

If (V2)\binom{V}{2} denotes the set of two-element subsets of VV, a signed graph could be equivalently defined to be a set VV together with a partial function (V2){+,}\binom{V}{2} \to \{+, -\}. The domain of this partial function is declared to be EE, so the data of a signed graph can be represented as VV together with a span of type

(V2)Eσ{+,}.\binom{V}{2} \hookleftarrow E \stackrel{\sigma}{\to} \{+, -\}.

Signed graphs should not be regarded as directed graphs: signs on undirected edges are not the same as directional information. For example, if vertices represent people and edges represent being acquainted then the signs could indicate being allies or enemies.

If a linear order has been imposed on the vertex set, then the sign function can be interpreted as imparting directions to edges (say if x<yx \lt y in the order and an edge ee between xx and yy has sign ++, then the direction is xyx \to y; if ee has sign -, then the direction is yxy \to x). However, such linear orders on vertices will not be preserved by morphisms of signed graphs, so this does not give a functorial way to derive directed graphs from signed graphs.

Signed graphs (and the basic theorems of their theory) seem to be rediscovered again and again. See Zaslavsky for an annotated bibliography on signed graphs and their various guises.


Last revised on August 26, 2017 at 11:52:46. See the history of this page for a list of all contributions to it.