Two simple graphs are isomorphic if there is some bijection between the vertex sets and edges are preserved under this mapping. Can this also work for multigraphs? I think that the same definition can be used because we are only adding more edges.

  • 2
    $\begingroup$ It can "also work for multigraphs", though you should give a definition for what you mean by that term. Most likely you have in mind the possibility that two vertices can share more than one edge, but there are other generalizations of "simple graphs" to which a notion of isomorphism can be extended. $\endgroup$ – hardmath Jan 22 '18 at 18:13

Yes and no.

I assume that by "multigraph" you mean a graph where you allow more than one edge between each pair of vertices.

In that case you can certainly say that $G$ and $H$ are isomorphic iff there is a bijection $f:V(G)\to V(H)$ such that for every $v,u\in V(G)$, the number of $H$-edges from $f(u)$ to $f(v)$ is the same as the number of $G$-edges from $u$ to $v$.

However, when you speak about an isomorphism between $G$ and $H$, you would usually want that to be a combination of a function that maps vertices to vertices and a function that tells exactly which edges in $G$ maps to which edges in $H$. For example if $G$ and $H$ are both directed graphs with $2$ vertices and exactly $2$ parallel edges from one vertex to the other, then there would be two different isomorphisms between $G$ and $H$, depending on which edges map to which.

  • $\begingroup$ Yes that is what a multigraph represents for me. Makes sense that we don't know which edge is mapped to which one exactly! However, as long as there is one bijective mapping, we can say that they are isomorphic right? $\endgroup$ – mandella Jan 23 '18 at 8:09
  • 1
    $\begingroup$ @mandella: Yes; to say that two things "are isomorphic" is just to say that there exists at least one isomorphism between them. So for that you just need to count edges. $\endgroup$ – Henning Makholm Jan 23 '18 at 13:05

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.