Let $G(V,E)$ and $H(V',E')$ be two undirected graphs. Suppose $f : V \to V'$ is a function such that $\forall (u,v) \in V\times V, (u,v)\in E \implies (f(u),f(v))\in E' $ and $\forall (u,v) \in V\times V, (u,v)\notin E \implies (f(u),f(v))\notin E' $. In otherwords $f$ preserves edges as well as non-edges of $G$. But it need not be the case that $f$ is injective.

Note that $f$ by definition is a homomorphism from $G$ to $H$. But it is clearly a stricter notion. Is there a name for such morphisms ? And are there results on combinatorics of such morphisms ?

  • $\begingroup$ So if $f:G\to H$ is such a strict homomorphism, it means that $G$ can be obtained from $H$ in two steps, first passing to an induced subgraph, and then splitting vertices? In other words, $f$ is the composition of two maps, the first identifies some vertices with identical neighborhoods, and the second is an isomorphic embedding? Have I got that right? $\endgroup$ – bof Oct 16 '14 at 12:01
  • $\begingroup$ Since your strict homomorphism is a homomorphism, the preimage of a vertex is a coclique. Since your homomorphism is strict, its restriction to a coclique must be injective. Therefore a strict homomorphism is an isomorphism. Perhaps I am missing something? $\endgroup$ – Chris Godsil Oct 16 '14 at 12:26
  • $\begingroup$ @bof yes . In fact we obtain it exactly like that. We wanted to know if such compositions are already studied under some will known name. Especially counts of such morphisms. Chris Godsil bof'sanswer gives you such an example where it is not an isomorphism. The most trivial example would be to make the requirement on non edges vacously true by choosing $ K_n $ and $ K_m $. For a non trivial example consider a $ K_{2, 3}$ and $ K_{1, 3}$. If $ H $ has no self loops $ u, v \notin E $ can have $ f (u)=f (v) $. $\endgroup$ – Sajin Koroth Oct 16 '14 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.