Graph Injective-Homomorphism Problem

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.

• 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.
– D.W.
Commented May 10, 2022 at 18:22
• 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.
– D.W.
Commented May 10, 2022 at 21:08
• You are right. Injective-homomorphism is same as subgraph isomorphism (which allows for extra edges in H; induced subgraph isomorphism doesn't). Commented May 10, 2022 at 23:35

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

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.