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