2
$\begingroup$

Let $G$ and $H$ be graphs. Is there a name for a function $f$ which

  1. Maps each vertex $x$ of $G$ to a vertex $f(x)$ of $H$
  2. Maps each edge $e \in E(G)$ with endpoints $x$ and $y$ to a path $f(e)$ between $f(x)$ and $f(y)$

In other words, $f$ is like a graph homomorphism, but edges can be mapped to any path with the right endpoints.

$\endgroup$
  • $\begingroup$ Yeah, I've missed that you want edges-to-paths mapping. This is a weird requirement to be honest. It seems like this is the same as graph homomorphism $G\to P(H)$ where $P(H)$ is the graph with the same vertices as $H$ but there's an edge for each path in $H$. $\endgroup$ – freakish Jun 26 at 12:05
  • 3
    $\begingroup$ @Aryadeva What do you mean what have I tried? I'm writing a proof that uses this and I'm wondering if there's a standard name for this... $\endgroup$ – David Dima Jun 26 at 12:07
  • $\begingroup$ @freakish The idea is that the edges in the graph represent basic transformations between certain states, and paths represent more complex transformations that are composed of several basic transformations. So in this case the right concept of homomorphism should be allowed to reduce what's considered a basic transformation in one graph, to a sequence of basic transformations in another. $\endgroup$ – David Dima Jun 26 at 12:09
  • $\begingroup$ Sorry the comment wasn'r meant for this question but for another one. Sorry. $\endgroup$ – Aryadeva Jun 26 at 12:46
3
$\begingroup$

A functor. If you treat the graphs as categories, where the objects are vertices, morphisms are paths, and composition is path concatenation, then what you describe is a functor between the graphs.

You also say in the comments:

The idea is that the edges in the graph represent basic transformations between certain states, and paths represent more complex transformations that are composed of several basic transformations.

This is exactly what categories are used for.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

This is a homomorphism from a subdivision of $G$ to $H$.

You probably want the homomorphism to be injective, because otherwise there are almost always uninteresting maps of this type. In the injective case, we more commonly say that there is a subgraph of $H$ which is a subdivision of $G$. (You can see this used, for example, in Kuratowski's theorem.)

| cite | improve this answer | |
$\endgroup$

Your Answer

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

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