PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (190)
Orphanage
Unclass'd (1)
Unproven (496)
Corrections (7)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
graph homomorphism (Definition)

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 $ 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:E\to 2^V$ is a map (incidence map), such that for every $ e\in E$, $ 1\le \vert i(e)\vert\le 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 endpoint(s) of $ e$. If an edge $ e$ has only one endpoint, it is called a loop. $ e_1$ and $ e_2$ are said to be parallel if $ i(e_1)=i(e_2)$.

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

Definition. Given two pseudographs $ G_1=(V_1,E_1,i_1)$ and $ G_2=(V_2,E_2,i_2)$, a graph homomorphism $ h$ from $ G_1$ to $ G_2$ consists of two functions $ f:V_1\to V_2$ and $ g:E_1\to E_2$, such that

$\displaystyle i_2\circ g=f^*\circ i_1.$     (1)

The function $ f^*:2^{V_1} \to 2^{V_2}$ is defined as $ f^*(S)=\lbrace f(s)\mid s\in S\rbrace$.

A graph isomorphism $ h=(f,g)$ is a graph homomorphism such that both $ f$ and $ g$ are bijections. It is a graph automorphism if $ G_1=G_2$.

Remarks.

  • In case when $ G_1$ and $ G_2$ are graphs, a graph homomorphism may be defined in terms of a single function $ f:V_1\to V_2$ satisfying the condition (*)
    $ \lbrace v_1,v_2\rbrace$ is an edge of $ G_1\Longrightarrow \lbrace f(v_1),f(v_2)\rbrace$ is an edge of $ G_2$.
    To see this, suppose $ h=(f,g)$ is a graph homomorphism from $ G_1$ to $ G_2$. Then $ f^*i_1(e)=f^*(\lbrace v_1,v_2\rbrace)=\lbrace f(v_1),f(v_2)\rbrace=i_2(g(e))$. The last equation says that $ f(v_1)$ and $ f(v_2)$ are endpoints of $ g(e)$. Conversely, suppose $ f:V_1\to V_2$ is a function sastisfying condition (*). For each $ e\in E_1$ with end points $ \lbrace v_1,v_2\rbrace$, let $ e^{\prime}\in E_2$ be the edge whose endpoints are $ \lbrace f(v_1),f(v_2)\rbrace$. There is only one such edge because $ G_2$ is a graph, having no parallel edges. Define $ g:E_1\to E_2$ by $ g(e)=e^{\prime}$. Then $ g$ is a well-defined function which also satisfies Equation (1). So $ h:=(f,g)$ is a graph homomorphism $ G_1\to G_2$.
  • 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,
    $\displaystyle \begin{xy} *!C\xybox{ \xymatrix{a \ar[r] & b\ar[d] \ c \ar[u] &... ...uad\qquad\qquad \xymatrix{r \ar[r] & s \ t \ar[u]\ar[r] & u\ar[u]} } \end{xy}$
    are two non-isomorphic digraphs whose underlying graphs are isomorphic. Note that one digraph is strongly connected, while the other is only weakly connected.



"graph homomorphism" is owned by CWoo.
(view preamble)

View style:

See Also: graph isomorphism, pseudograph, multigraph, graph

Other names:  graph automorphism
Log in to rate this entry.
(view current ratings)

Cross-references: strongly connected, digraphs, ordered pair, well-defined, end points, equation, terms, bijections, graph isomorphism, functions, one-to-one, parallel, loop, endpoint, vertices, map, edge, vertex, graphs, multigraphs, pseudographs
There are 3 references to this entry.

This is version 8 of graph homomorphism, born on 2006-07-13, modified 2007-05-24.
Object id is 8140, canonical name is GraphHomomorphism.
Accessed 2004 times total.

Classification:
AMS MSC: 05C60 (Combinatorics :: Graph theory :: Isomorphism problems )
 05C75 (Combinatorics :: Graph theory :: Structural characterization of types of graphs)
Pending Errata and Addenda
None.
[ View all 3 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)