4
$\begingroup$

When is it true that if $G$ is isomorphic to a spanning subgraph of $H$ and $H$ is isomorphic to a spanning subgraph of $G$, then $G$ is isomorphic to $H$?

Clearly this is true if $G$ and $H$ are finite graphs; however, this is not necessarily true for infinite graphs. For instance, let $G$ be an infinite clique together with infinitely many isolated vertices and let $H$ be two disjoint infinite cliques together with infinitely many isolated vertices. We posed this problem in Corsten, DeBiasio, and McKenney - Density of monochromatic infinite subgraphs II (see Problem 2.12), but since this question seems more basic and is only tangential to our results, I figured I would ask here as well.

Addendum 1: After doing some more digging, I found this related post Non-isomorphic graphs with bijective graph homomorphisms in both directions between them which just asked for examples of such graphs $G$ and $H$ where $G$ and $H$ are not isomorphic.

Addendum 2: There was a comment yesterday, which for some reason seems to have been deleted, suggesting the term "co-hopfian graph." I found this paper Cain and Maltcev - Hopfian and co-hopfian subsemigroups and extensions which defines co-hopfian graphs (see the paragraph before Lemma 4.5) as those in which every injective homomorphism from $G$ to $G$ (i.e. injective endomorphism) is an isomorphism. It's unclear to me if this makes a difference in the characterization, but I now believe my question is equivalent to "Which graphs $G$ have the property that every bijective homomorphism from $G$ to $G$ (i.e. bijective endomorphism) is an automorphism." Sorry to overdo it, but my original question has now become three questions:

  1. Which graphs $G$ have the property that every injective endomorphism is an automorphism? (equivalently, when is it true that if $G$ is isomorphic to a subgraph of $H$ and $H$ is isomorphic to a subgraph of $G$, then $G$ is isomorphic to $H$?)

  2. Which graphs $G$ have the property that every bijective endomorphism is an automorphism? (equivalently, when is it true that if $G$ is isomorphic to a spanning subgraph of $H$ and $H$ is isomorphic to a spanning subgraph of $G$, then $G$ is isomorphic to $H$?)

  3. Are the answers to 1 and 2 the same?

$\endgroup$
2
  • 2
    $\begingroup$ It's reasonably easy to find locally finite (but still disconnected) examples via a similar trick. For example if you take $G$ to be the collection of all odd length paths, together with countably many isolated vertices and $H$ to be the collection of all even length paths together with countably many isolated vertices, then they are both isomorphic to a spanning subgraph of the other. $\endgroup$ Jul 30 '20 at 8:28
  • 2
    $\begingroup$ The answers to 1 and 2 are not the same: A ray has injective endomorphisms which are not automorphisms (e.g. map every vertex to its successor), but the only bijective endomorphism is the identity. $\endgroup$ Jul 30 '20 at 23:11
5
$\begingroup$

This is an extended comment rather than an actual answer.

I think that any answer to your questions 1 and 2 is likely to be rather involved since the properties you ask are sensitive to small local changes in the graph. To illustrate what I mean, consider the following two graphs:

  1. $G_1$ has vertices $u_n, v_n$ for $n \in \mathbb Z$, and edges $u_nu_{n+1}$ and $u_{2n}v_n$ for $n \in \mathbb Z$, and $u_{2n+1}v_n$ for $n \in \mathbb N$.
  2. $G_2$ is obtained from $G_1$ by removing $v_0$.

Although these graphs are almost the same, they differ in terms of the properties you are asking:

$G_1$ has a bijective endomorphism which is not an isomorphism (defined by $u_n \mapsto u_{n+2}$ and $v_n \mapsto v_{n+1}$).

On the other hand, the only injective homomorphism from $G_2$ to itself is the identity: note that $v_0$ is a vertex of degree $2$ whose neighbours also have degree $\leq 2$, thus $v_0$ must be mapped to itself under any injective homomorphism. From there it is not hard to inductively show that the identity is the only injective endomorphism.

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