Skip to main content

Are there simple, undirected graphs $G, H$ that are non-isomorphic, but there exist graph homomorphisms $f_1: G\to H$ and $f_2: H\to G$ which are bijective set-maps $V(G)\rightarrow V(H)$ and $V(H)\rightarrow V(G)$?

NoteNotes. By the argument in Tobias Fritz's comment below, $G, H$ have to be infinite.

  • By the argument in Tobias Fritz's comment below, $G, H$ have to be infinite.

  • As suggested by a commenter, one should make it unambiguously clear that here, 'simple, undirected graph'='irreflexive symmetric binary relation on a set'.

Are there simple, undirected graphs $G, H$ that are non-isomorphic, but there exist graph homomorphisms $f_1: G\to H$ and $f_2: H\to G$ which are bijective set-maps $V(G)\rightarrow V(H)$ and $V(H)\rightarrow V(G)$?

Note. By the argument in Tobias Fritz's comment below, $G, H$ have to be infinite.

Are there simple, undirected graphs $G, H$ that are non-isomorphic, but there exist graph homomorphisms $f_1: G\to H$ and $f_2: H\to G$ which are bijective set-maps $V(G)\rightarrow V(H)$ and $V(H)\rightarrow V(G)$?

Notes.

  • By the argument in Tobias Fritz's comment below, $G, H$ have to be infinite.

  • As suggested by a commenter, one should make it unambiguously clear that here, 'simple, undirected graph'='irreflexive symmetric binary relation on a set'.

I clarified the question, giving it the only interpretation I can think of which does not make it vacuous.
Source Link

Non-isomorphic graphs with bijective graph homomorphisms in both directions between them

Are there simple, undirected graphs $G, H$ that are non-isomorphic, but there exist bijective graph homormophismshomomorphisms $f_1: G\to H$ and $f_2: H\to G$ which are bijective set-maps $V(G)\rightarrow V(H)$ and $V(H)\rightarrow V(G)$?

Note. By the argument in Tobias Fritz's comment below, $G, H$ have to be infinite.

Non-isomorphic graphs with bijective graph homomorphisms between them

Are there simple, undirected graphs $G, H$ that are non-isomorphic, but there exist bijective graph homormophisms $f_1: G\to H$ and $f_2: H\to G$?

Note. By the argument in Tobias Fritz's comment below, $G, H$ have to be infinite.

Non-isomorphic graphs with bijective graph homomorphisms in both directions between them

Are there simple, undirected graphs $G, H$ that are non-isomorphic, but there exist graph homomorphisms $f_1: G\to H$ and $f_2: H\to G$ which are bijective set-maps $V(G)\rightarrow V(H)$ and $V(H)\rightarrow V(G)$?

Note. By the argument in Tobias Fritz's comment below, $G, H$ have to be infinite.

added 90 characters in body
Source Link

Are there simple, undirected graphs $G, H$ that are non-isomorphic, but there exist bijective graph homormophisms $f_1: G\to H$ and $f_2: H\to G$?

Note. By the argument in Tobias Fritz's comment below, $G, H$ have to be infinite.

Are there simple, undirected graphs $G, H$ that are non-isomorphic, but there exist bijective graph homormophisms $f_1: G\to H$ and $f_2: H\to G$?

Are there simple, undirected graphs $G, H$ that are non-isomorphic, but there exist bijective graph homormophisms $f_1: G\to H$ and $f_2: H\to G$?

Note. By the argument in Tobias Fritz's comment below, $G, H$ have to be infinite.

Source Link
Loading