Is a morphism between graphs that doesn't respect adjacency a homomorphism but not a graph homomorphism?

Question

Is a morphism between graphs that doesn't respect adjacency a homomorphism (but not a graph homomorphism)?

For example consider the morphisms $M$ on the complete binary rooted tree $T$ of dyadic rationals in the interval $(0,1)$:

$T=\{E,V\}$

$E=\{\{\frac{1}{2},\frac{1}{4}\},\{\frac{1}{2},\frac{3}{4}\},\{\frac{1}{4},\frac{1}{8}\},\{\frac{1}{4},\frac{3}{8}\},\{\frac{3}{4},\frac{5}{8}\},\{\frac{3}{4},\frac{7}{8}\},\{\frac{1}{8},\frac{1}{16}\},\ldots\}$

Then there's a morphism $M_{gh}$ that exchanges $\{\frac{1}{4},\frac{3}{4}\}$ and all of their children. This preserves adjacency and is a graph homomorphism.

However there's also a morphism $M_h$ that exchanges $\{\frac{1}{8},\frac{3}{4}\}$. The resulting graph $M_h(T)$ continues to have exactly the same shape & structure, i.e. it's a complete, infinite, binary rooted tree. Only the eighths (in lowest terms) are no longer adjacent to the quarters (and so on for their children).

Am I right to understand this is simply called a homomorphism between graphs, but is not called a graph homomorphism because it fails to preserve adjacency and distance between vertices? Is there a better name?

Seems to have the potential to cause confusion.

EDIT: Actually, reading more extensively it looks like the topological definition of homeomorphism between graphs is weaker than the morphism I describe because for example in a homeomorphism by that definition, vertices of order $2$ and their two edges can be removed leaving a single edge, and the graphs be topologically homomorphic, but this change wouldn't preserve a complete, infinite, binary, rooted tree.

Candidate for the name of such a map: A permutation of vertices?

Answer 1

This seems to be a matter of terminology. According to Wikipedia a graph homomorphism from $G$ to $H$ is a function from $V(G)$ to $V(H)$ which preserves adjacency. You can still consider functions that don't preserve adjacency, and call them what you will, but not graph homomorphisms because that contradicts their characteristic property and to avoid confusion. This is true for any concrete category where the morphisms are structure-preserving functions. You can consider functions defined on the underlying sets, but if they don't preserve the structure, they are not morphisms.

Answer 2

You seem to be confused about what is a "morphism". A "morphism" is just an arrow in some category.

When we discuss the category of graphs, the objects are graphs, and the morphisms are graph homomorphisms. But a graph can canonically be turned into a topological space by replacing each edge of the graph by a copy of the unit interval, turning it into a simplicial $1$-complex. (See this for a slightly more detail description.) So you can see a map between the vertices and edges of two graphs in two ways : assuming that a map $f : G_1 \to G_2$ is such that if $v_1,v_2$ in $G_1$ are linked by an edge, $f(v_1)$ and $f(v_2)$ are linked by an edge (i.e. $f$ is a morphism of graphs), you can think of $f$ as a morphism of graphs or as a morphism of the corresponding topological spaces.

Now that you know this, note that

• A graph isomorphism is a morphism of graphs which is bijective on vertices and edges.

• A homeomorphism is a map of topological spaces between the underlying topological structures on the graphs which is bijective and where the inverse map is also continuous.

I couldn't figure out correctly what you are exactly struggling on, but I have two candidates :

• What you called a "graph homeomorphism" seems to be a morphism of graphs which is a homeomorphism but not necessarily an isomorphism (because graph isomorphisms are of course homeomorphisms, so you seemed to think that graph homeomorphisms are not necessarily isomorphisms).

• Maybe you are confusing the word "homomorphism" and "homeomorphism" ; the latter is much stronger since it means "isomorphism of topological spaces" whereas homomorphism is essentially the word "morphism" in some categories.

Feel free to ask me more questions in the comments if you are still confused about everything.

Hope that helps,