Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 3 down vote accepted

(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$.

share|improve this answer
    
Nicely explained ... :-) I got my doubts cleared now. Thanks a lot sir. –  monalisa May 31 '13 at 4:20
    
@monalisa: You’re welcome. –  Brian M. Scott May 31 '13 at 6:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.