Two graphs $G$ and $G^{\prime}$ are said to be graph isomeric if the share the same number of vertices and edges. If there is a graph homomorphism $h \colon G \to G^{\prime}$ between graph isomers which preserves vertex degree, can one conclude that $G$ and $G^{\prime}$ are graph isomorphic?

  • 1
    $\begingroup$ I never know what people's conventions for graph homomorphisms are. Are they just maps from vertices to vertices that preserve the relation given by edges? Are vertices considered related to themselves for the purposes of this relation? $\endgroup$ – Qiaochu Yuan Aug 6 '12 at 17:06
  • 1
    $\begingroup$ I'm using this definition of homomorphism. $\endgroup$ – user02138 Aug 6 '12 at 17:21

$$1-2-1 \quad 1-2-1$$

is not isomorphic with $$1-1 \quad 1-2-2-1$$

But they are isomeric and there is a trivial homomorphism. There are plenty of other examples...

  • $\begingroup$ Sorry, what is the homomorphism which preserves vertex degrees? $\endgroup$ – Qiaochu Yuan Aug 6 '12 at 17:07
  • $\begingroup$ just the 2's onto the 2's and the 1's onto the 1's $\endgroup$ – Xoff Aug 6 '12 at 17:10
  • $\begingroup$ Oh, I see. I didn't understand how you were mapping the vertices of degree $1$ but it is clear now. $\endgroup$ – Qiaochu Yuan Aug 6 '12 at 17:12
  • $\begingroup$ What if we add "connected" to the assumptions? $\endgroup$ – user02138 Aug 6 '12 at 17:13
  • 4
    $\begingroup$ 2-3-2 and 3-2-2, just complete with 1s where needed... $\endgroup$ – Xoff Aug 6 '12 at 17:17

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.