<p>In the case of undirected graphs, there is literature about such morphisms called <strong>graph emulators</strong>.
They are a refinement of the notion of covering graph.
A covering graph maps the neighbourhood of a vertex $u$ bijectively to the neighbourhood of $h(u)$, while an emulator is only required to do it surjectively, which seems equivalent to your question.</p>

<p>This notion appears in the context of characterizing graphs having planar covers or planar emulators, which yields several open problems, see for instance <a href="http://www.fi.muni.cz/~hlineny/papers/plcover20-gc.pdf" rel="nofollow">this paper</a> for a survey.</p>

CC BY-SA 3.0
2015-12-14T19:13:18.463Z
Thank you! That helps a lot. In the paper one finds the alternative term "branched covering".
Thomas S
CC BY-SA 3.0
2015-12-14T14:49:33.947Z
2015-12-14T14:49:33.947Z
Denis
<p>Let $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ be graphs and let $h:V_2\to V_1$ be a map such that, for every edge $(u_1,v_1)\in E_1$, there is an edge $(u_2,v_2)\in E_2$ such that $h(u_2)=u_1$ and $h(v_2)=v_1$.</p>

<p>This kind of maps has occurred in our recent research in Database Theory. We think that it looks like a natural "dual" to graph homomorphisms, where $h$ would be $V_1\to V_2$ and map each edge of $G_1$ to an edge of $G_2$. However, we could not find it in the literature, but, since we do not have a name for it, maybe we searched in the wrong places.</p>

<p>Some background: in Database Theory, homomorphisms play an important role in the context of the containment problem for conjunctive queries. The "kind-of-dual" form occurs in the context of parallel query evaluation. </p>

<p>In this slightly extended context, testing for existence of such a mapping is NP-complete, and I expect that also for graphs. However, I am not asking for complexity results, but I would be be grateful for pointers to the literature (or even a <em>name</em>, for that matter).</p>

CC BY-SA 3.0
2015-12-14T13:44:11.087Z
This is usually expressed by saying that the map *reflects* the existence of edges (or other relations) rather than *preserving* them as a homomorphism would. In this case, you could also say that for every non-edge $(u_2,v_2)$, $(h(u_2),h(v_2))$ is also a non-edge, i.e. $h$ is a homomorphism of the complements.
Klaus Draeger
CC BY-SA 3.0
2015-12-14T19:18:02.147Z
Thank you. Oh yeah! Now I ask myself why I haven't seen the complement characterization. ;-) 
The downside is that for the complexity the detour through the complement will not help a lot, since this is usually  of exponential size. 
In any case, this helped.
Thomas S
CC BY-SA 3.0
2015-12-15T10:37:35.553Z
@KlausDraeger, I don't follow. $P_3$ maps to $P_2+v$ via a non-bijective map $h$ of the kind in the question, but $h$ is not a homomorphism from the complement $P_2+v$ to the complement $P_3$. Are you considering graphs with self-loops?
András Salamon
CC BY-SA 3.0
2015-12-15T12:10:50.700Z
@AndrásSalamon good point, for the "homomorphism of complements" description you need to allow self-loops (or restrict yourself to injections).
Klaus Draeger
<co.combinatorics>
Has this form of "kind-of-dual" homomorphisms been studied?
Thomas S
# Has this form of "kind-of-dual" homomorphisms been studied?

(Asked by: username_0 on 2015-12-14)

Let $G\_1=(V\_1,E\_1)$ and $G\_2=(V\_2,E\_2)$ be graphs and let $h:V\_2\to V\_1$ be a map such that, for every edge $(u\_1,v\_1)\in E\_1$, there is an edge $(u\_2,v\_2)\in E\_2$ such that $h(u\_2)=u\_1$ and $h(v\_2)=v\_1$.

This kind of maps has occurred in our recent research in Database Theory. We think that it looks like a natural "dual" to graph homomorphisms, where $h$ would be $V\_1\to V\_2$ and map each edge of $G\_1$ to an edge of $G\_2$. However, we could not find it in the literature, but, since we do not have a name for it, maybe we searched in the wrong places.

Some background: in Database Theory, homomorphisms play an important role in the context of the containment problem for conjunctive queries. The "kind-of-dual" form occurs in the context of parallel query evaluation.

In this slightly extended context, testing for existence of such a mapping is NP-complete, and I expect that also for graphs. However, I am not asking for complexity results, but I would be be grateful for pointers to the literature (or even a *name*, for that matter).

**Tags:** co.combinatorics
> **Comments:**
> **username_1**: This is usually expressed by saying that the map *reflects* the existence of edges (or other relations) rather than *preserving* them as a homomorphism would. In this case, you could also say that for every non-edge $(u_2,v_2)$, $(h(u_2),h(v_2))$ is also a non-edge, i.e. $h$ is a homomorphism of the complements.  
> **username_0**: Thank you. Oh yeah! Now I ask myself why I haven't seen the complement characterization. ;-)  The downside is that for the complexity the detour through the complement will not help a lot, since this is usually  of exponential size.  In any case, this helped.  
> **username_2**: @KlausDraeger, I don't follow. $P_3$ maps to $P_2+v$ via a non-bijective map $h$ of the kind in the question, but $h$ is not a homomorphism from the complement $P_2+v$ to the complement $P_3$. Are you considering graphs with self-loops?  
> **username_1**: @AndrásSalamon good point, for the "homomorphism of complements" description you need to allow self-loops (or restrict yourself to injections).  

---

## 1 answers

### Answer by username_3 on 2015-12-14. Score: 3 | Accepted answer

In the case of undirected graphs, there is literature about such morphisms called **graph emulators**.
They are a refinement of the notion of covering graph.
A covering graph maps the neighbourhood of a vertex $u$ bijectively to the neighbourhood of $h(u)$, while an emulator is only required to do it surjectively, which seems equivalent to your question.

This notion appears in the context of characterizing graphs having planar covers or planar emulators, which yields several open problems, see for instance [this paper](http://www.fi.muni.cz/~hlineny/papers/plcover20-gc.pdf) for a survey.

> **Comments:**
> **username_0**: Thank you! That helps a lot. In the paper one finds the alternative term "branched covering".  

---

