Expanding definition of simple graph isomorphism to include multigraphs

760 Views Asked by At

I've defined isomorphism from one graph $G$ to another graph $K$ as follows:

An isomorphism is a bijective function $f$ from the vertices of $G$ to the vertices of $K$, such that the vertices $u$ and $v$ are neighbours in $G$ if and only if the vertices $f(u)$ and $f(v)$ are neighbours in $K$.

However, this definition only holds for simple graphs (graphs with no loops/parallel edges).

How can I change this definition to also include multigraphs?

1

There are 1 best solutions below

2
On BEST ANSWER

I googled a bit for a definition of isomorphic mutigraphs, but found none. So I propose to naturally extend a notion of graph isomorphism to multigraphs as follows. For each multigraph $G$ with a vertex set $V$. For each $v,u\in V$ let $l(v)$ be the number of loops at vertex $v$ and $e(u,v)$ be the number of edges between $v$ and $u$. Then an isomorhism between multigraphs $G$ with a vertex set $V(G)$ and $H$ with a vertex set $V(H)$ is a bijection $f$ between $V(G)$ and $V(H)$ such that for each $v,u\in V$ holds $l(v)=l(f(v))$ and $e(u,v)=e(f(u),f(v))$.