graph homomorphism


We shall define what a graph homomorphism is between two pseudographsMathworldPlanetmath, so that a graph homomorphism between two multigraphsMathworldPlanetmath, or two graphs are special cases.

Recall that a pseudograph G is an ordered triple (V,E,i), where V is a set called the vertex set of G, E is a set called the edge set of G, and i:E2V is a map (incidence map), such that for every eE, 1|i(e)|2.

Elements of V are called vertices, elements of E edges. The vertex/vertices associated with any edge e via the map i is/are called the endpointMathworldPlanetmath(s) of e. If an edge e has only one endpoint, it is called a loop. e1 and e2 are said to be parallelMathworldPlanetmathPlanetmath if i(e1)=i(e2).

As two examples, a multigraph is a pseudograph such that |i(e)|=2 for each edge eE (no loops allowed). A graph is a multigraph such that i is one-to-one (no parallel edges allowed).

Definition. Given two pseudographs G1=(V1,E1,i1) and G2=(V2,E2,i2), a graph homomorphism h from G1 to G2 consists of two functions f:V1V2 and g:E1E2, such that

i2g=f*i1. (1)

The function f*:2V12V2 is defined as f*(S)={f(s)sS}.

A graph isomorphismMathworldPlanetmath h=(f,g) is a graph homomorphism such that both f and g are bijectionsMathworldPlanetmath. It is a graph automorphism if G1=G2.

Remarks.

  • In case when G1 and G2 are graphs, a graph homomorphism may be defined in terms of a single function f:V1V2 satisfying the condition (*)

    {v1,v2} is an edge of G1{f(v1),f(v2)} is an edge of G2.

    To see this, suppose h=(f,g) is a graph homomorphism from G1 to G2. Then f*i1(e)=f*({v1,v2})={f(v1),f(v2)}=i2(g(e)). The last equation says that f(v1) and f(v2) are endpoints of g(e). Conversely, suppose f:V1V2 is a function sastisfying condition (*). For each eE1 with end points {v1,v2}, let eE2 be the edge whose endpoints are {f(v1),f(v2)}. There is only one such edge because G2 is a graph, having no parallel edges. Define g:E1E2 by g(e)=e. Then g is a well-defined function which also satisfies Equation (1). So h:=(f,g) is a graph homomorphism G1G2.

  • The definition of a graph homomorphism between pseudographs can be analogously applied to one between directed pseudographs. Since the incidence map i now maps each edge to an ordered pair of vertices, a graph homomorphism thus defined will respect the “direction” of each edge. For example,

    \xymatrixa\ar[r]&b\ar[d]c\ar[u]&d\ar[l]        \xymatrixr\ar[r]&st\ar[u]\ar[r]&u\ar[u]

    are two non-isomorphic digraphsMathworldPlanetmath whose underlying graphs are isomorphic. Note that one digraph is strongly connectedPlanetmathPlanetmath, 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