nLab signed graph





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

One says that the sign of a cycle in a signed graph is the product of the signs of its edges.

There are several notions of homomorphisms of signed graphs. They are all homomorphisms of the underlying graphs, by differ by how strictly they preserve the extra sign structure:

  1. sign preserving homomorphisms preserve the signs of individual edges,

  2. switching homomorphisms are only required to preserve the signs of cycles but not necessarily of individual edges.


Let (V2)\binom{V}{2} denotes the set of two-element subsets of VV. A signed simple graph is equivalently 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 \overset{\sigma}{\longrightarrow} \{+, -\} \,.

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


Signed graphs are not 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.


  • Thomas Zaslavsky, A Mathematical Bibliography of Signed and Gain Graphs and Allied Areas, Electronic Journal of Combinatorics, Dynamic Surveys in Combinatorics, DS8 (2018) [doi:10.37236/29]

Last revised on January 14, 2024 at 06:06:16. See the history of this page for a list of all contributions to it.