Projections in Graph Products

Question

I was going throug the topic Projections in Graph Products. There a term weak homomorphism was used. Although I am familiar with the term Isomorphism of graphs, but have no idea what this term "weak homomorphism" means here.

PROJECTION: Let * represent either cartesian, the direct or strong product of graphs, and consider a product $G_1 * G_2* ....*G_k$. For any index i 1$\leq$*i*$\leq$*k*, a Projection map is defined as :

$p_i$ : $G_1 * G_2* ....*G_k$ $\rightarrow$ $G_i$ where $p_i$($x_1,x_2,...,x_k$)=$x_i$.

Can anybody help me out with the term weak homomorphism.

Thanks a lot.

Following links will help for definiton of product graphs... http://en.wikipedia.org/wiki/Tensor_product_of_graphs http://en.wikipedia.org/wiki/Cartesian_product_of_graphs http://en.wikipedia.org/wiki/Strong_product_of_graphs

Answer 1

(We don’t actually need to know about the graph products in order to answer the question.)

If $G$ and $H$ are graphs with vertex sets $V(G)$ and $V(H)$, respectively, a homomorphism from $G$ to $H$ is a map $\varphi:V(G)\to V(H)$ that preserves adjacency: if $uv$ is an edge in $G$, then $\varphi(u)\varphi(v)$ is an edge in $H$. A weak homomorphism from $G$ to $H$ is a map $\varphi:V(G)\to V(H)$ such that if $uv$ is an edge in $G$, then either $\varphi(u)\varphi(v)$ is an edge in $H$, or $\varphi(u)=\varphi(v)$. In other words, if $\varphi$ is a weak homomorphism from $G$ to $H$, and $e$ is an edge in $G$, $\varphi$ either preserves $e$ as an edge by collapses it to a single vertex. Clearly every homomorphism is automatically a weak homomorphism.

In the diagram below let $G$ be the path graph on the left and $H$ the triangle graph on the right.

           1---2---3                a---b  
                                     \ /  
                                      c

The map

$$\left\{\begin{align*} 1&\mapsto a\\ 2&\mapsto b\\ 3&\mapsto c \end{align*}\right.$$

is a homomorphism from $G$ to $H$ is a homomorphism. The map

$$\left\{\begin{align*} 1&\mapsto a\\ 2&\mapsto b\\ 3&\mapsto b \end{align*}\right.$$

is not a homomorphism, because it does not take the edge $23$ of $G$ to an edge of $H$, but it is a weak homomorphism: it collapses that edge to the single vertex $b$ of $H$.