2
$\begingroup$

Graph Homomorphism is a well-known NP-complete problem. Given graph $G$ and $H$, $G$ is said to be homomorphic to $H$ if there is a mapping $f: V(G) \mapsto V(H)$ such that $(u,v) \in E(G) \implies (f(u), f(v)) \in E(H)$.

The mapping in above is unrestricted -- and hence, multiple nodes of $G$ can map to a single node in $H$. If we restrict the mapping to be injective, then only one node of $G$ can map to a node in $H$. Thus, we have the injective-homomorphism variant:

Given graph $G$ and $H$, $G$ is said to be injective-homomorphic to $H$ if there is an injective mapping $f: V(G) \mapsto V(H)$ such that $(u,v) \in E(G) \implies (f(u), f(v)) \in E(H)$.

To me -- the injective homomorphic is a very natural variant of Graph Homomorphism problem, but I am unable to find a single research paper on it (the closest is "locally injective" homomorphisms). Why has there been zero interest in Injective-Homomorphism? Could I be missing something? BTW, its easy to see that injective-homomorphism decision problem is also NP-complete, by a simple reduction from the Homomorphism problem.

$\endgroup$
3
  • 4
    $\begingroup$ This is also related to the subgraph isomorphism problem. In particular, if there is such an injection, then $(f(V(G)),f(E(G)))$ (a subgraph of $H$) is similar to $G$, except that it might have additional edges. Your problem might be related to subgraph monomorphism but I'm not certain about that. $\endgroup$
    – D.W.
    May 10, 2022 at 18:22
  • 1
    $\begingroup$ Yup - but does monomorphism allow for additional edges? I have never understand that part of this problem space so I might be talking nonsense - I apologize if this is not helpful. $\endgroup$
    – D.W.
    May 10, 2022 at 21:08
  • $\begingroup$ You are right. Injective-homomorphism is same as subgraph isomorphism (which allows for extra edges in H; induced subgraph isomorphism doesn't). $\endgroup$
    – Brian
    May 10, 2022 at 23:35

2 Answers 2

5
$\begingroup$

As D.W. mentioned, $G$ is injective-homomorphic to $H$ if and only if $G$ is isomorphic to a subgraph of $H$. That is why you are "unable to find a single research paper on 'injective-homomorphism'". There are plenty of paper about subgraphs or about subgraph isomorphism, of course.


More specifically, suppose we are given graph $G$ and $H$ and an injective-homomorphism from $G$ to $H$ $f: G\to H$, i.e., $f|_{V(G}:V(G) \to V(H)$ is injective and, $(u,v) \in E(G) \implies (f(u), f(v)) \in E(H)$. Then $f(G):=(f(V(G)),f(E(G)))$ is a subgraph of $H$. Moreover, the map $f: G\to f(G)$ is a graph isomorphism.

Conversely, if there is a graph isomorphism $f: G\to S$ where $S$ is a subgraph of $H$, then the composition of $f$ with the natural inclusion of $S$ into $H$ is an "injective-homomorphism" from $G$ to $H$.

$\endgroup$
0
1
$\begingroup$

If the homomorphism from a graph $G$ to a graph $H$ is injective, then $G$ is isomorphic to a subgraph of $H$. An injective homomorphism is called a monomorphism. Perhaps you can search for research papers on specific types of injective homomorphisms, such as co-retractions or isometric embeddings.

Given any homomorphism $f$ from $G$ to $H$, we can construct an injective homomorphism $\psi$ from the quotient $G/P$ to $H$ and a map $\pi_P$ such that $f = \psi \cdot \pi_P$. Here, $P$ is the partition of $V(G)$ obtained from the equivalence relation $x \sim y$ if and only if $f(x)=f(y)$, the quotient $G/P$ is defined to have vertex set $P$ and two vertices $V_i$ and $V_j$ are adjacent in this quotient whenever they each contain vertices that are adjacent in $G$, and $\pi_P: V(G) \rightarrow V(G/P)$ maps each vertex of $G$ to the part it belongs to.

A map $f:V(G) \rightarrow V(H)$ is an isometric embedding if it preserves distances in the sense that $d_H(f(u),f(v)) = d_G(u,v)$ for any two vertices $u,v \in V(G)$. Thus, an isometric embedding is a special type of injective homomorphism; it arises in the context of routing problems.

See (Hahn and Tardif, "Graph Homomorphisms: structure and symmetry") for properties of isometric embeddings and co-retractions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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