Site

Homomorphisms Of Signed Graphs

Definition (general one: loops and multiedges are allowed)

Homomorphism of a signed graph (G, 𝛴 ) to (H, Π ) is a mapping of both vertices and edges of G to vertices and edges of H (respectively) which preserves: 1. adjacencies, 2. incidences, 3. balance of closed-walks.

Remark

The mapping to be mapping of both vertices and edges is needed when we allow multiple-edges and specially digons. In such cases, if vertices u and v of H induce a digon and a pair x, y of adjacent vertices of G is mapped to u and v, then we must specify to which of the two uv edges the edge xy is mapped to.

Definition (multi-edges are not allowed)

A homomorphism of a signed graph (G, 𝛴 ) to (H, Π ) is a mapping of the vertices of G to the vertices of H under which each closed-walk of G is mapped to a closed-walk of the same length and the same balance. (:tableend:)

Remark

As each edge induces two closed-walks of length 2 which are always balanced and as the edge on the images are determined by the vertices of the walk (due to the fact that H has no multi-edge) the condition that closed-walks on length 2 maps to closed-walks of length 2 implies that adjacent vertices map to adjacent vertices in our definition, thus extending the classic definition of homomorphisms (simple) graphs. (:tableend:)

Notation

  • When there is a homomorphism of a (G, 𝛴 ) to (H, Π ) we write: (G, 𝛴 ) --> (H, Π ).

  • Let φ be a mapping of (G, 𝛴 ) to (H, Π ). Let 𝛴' be the set of edges of G that are mapped to Π . Then it follows from Zaslavsky's theorem that 𝛴' is a resigning of 𝛴' . Conversely if 𝛴' is a resigning of 𝛴 a mapping of G to H which preserves signs with respect to 𝛴' and Π is a homomorphism of (G, 𝛴 ) to (H, Π ).

  • A mapping φ of (G, 𝛴 ) to (H, Π ) can then be presented as a function φ : V(G) --> {+,-}⨯V(H).
    Written as φ=(φ1, φ2), the component φ1(v) decides if there has been a resigning at v in order to get 𝛴'.
    Then the component φ2 decides to which vertex of H the vertex v is mapped to.