graph homomorphism
We shall define what a graph homomorphism is between two pseudographs, so that a graph homomorphism between two multigraphs, or two graphs are special cases.
Recall that a pseudograph is an ordered triple , where is a set called the vertex set of , is a set called the edge set of , and is a map (incidence map), such that for every , .
Elements of are called vertices, elements of edges. The vertex/vertices associated with any edge via the map is/are called the endpoint(s) of . If an edge has only one endpoint, it is called a loop. and are said to be parallel if .
As two examples, a multigraph is a pseudograph such that for each edge (no loops allowed). A graph is a multigraph such that is one-to-one (no parallel edges allowed).
Definition. Given two pseudographs and , a graph homomorphism from to consists of two functions and , such that
(1) |
The function is defined as .
A graph isomorphism is a graph homomorphism such that both and are bijections. It is a graph automorphism if .
Remarks.
-
•
In case when and are graphs, a graph homomorphism may be defined in terms of a single function satisfying the condition (*)
is an edge of is an edge of .
To see this, suppose is a graph homomorphism from to . Then . The last equation says that and are endpoints of . Conversely, suppose is a function sastisfying condition (*). For each with end points , let be the edge whose endpoints are . There is only one such edge because is a graph, having no parallel edges. Define by . Then is a well-defined function which also satisfies Equation (1). So is a graph homomorphism .
-
•
The definition of a graph homomorphism between pseudographs can be analogously applied to one between directed pseudographs. Since the incidence map now maps each edge to an ordered pair of vertices, a graph homomorphism thus defined will respect the “direction” of each edge. For example,
are two non-isomorphic digraphs whose underlying graphs are isomorphic. Note that one digraph is strongly connected, while the other is only weakly connected.
Title | graph homomorphism |
Canonical name | GraphHomomorphism |
Date of creation | 2013-03-22 16:04:53 |
Last modified on | 2013-03-22 16:04:53 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 11 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 05C75 |
Classification | msc 05C60 |
Synonym | graph automorphism |
Related topic | GraphIsomorphism |
Related topic | Pseudograph |
Related topic | Multigraph |
Related topic | Graph |