3
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – Klaus Draeger
    Dec 14, 2015 at 13:44
  • $\begingroup$ 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. $\endgroup$
    – Thomas S
    Dec 14, 2015 at 19:18
  • $\begingroup$ @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? $\endgroup$
    – András Salamon
    Dec 15, 2015 at 10:37
  • $\begingroup$ @AndrásSalamon good point, for the "homomorphism of complements" description you need to allow self-loops (or restrict yourself to injections). $\endgroup$
    – Klaus Draeger
    Dec 15, 2015 at 12:10

1 Answer 1

Reset to default
3
$\begingroup$

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 for a survey.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! That helps a lot. In the paper one finds the alternative term "branched covering". $\endgroup$
    – Thomas S
    Dec 14, 2015 at 19:13

Your Answer

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

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