isomorphism of graph definition

751 Views Asked by At

In Douglas West's book of graph theory, this is how isomorphism of graphs is defined. Please note that graphs need not be simple.

An isomorphism from $G$ to $H$ is a bijection $f$ that maps $V(G)$ to $V(H)$ and $E(G)$ to $E(H)$ such that each edge of $G$ with end points $u$ and $v$ is mapped to an edge with endpoints $f(u)$ and $f(v)$.

Though I get the idea what author seems to say, however I feel the definition is ambiguous in sense that $f: G \to H$. Hence $f(u)$, $f(v)$ does not make any sense.

Query 1 : Please tell me how right am I in judging the above definition.

Query 2 : Here below I propose my own definition of isomorphism which seems to me a little bit more clear. Please tell me if it is right or not.

Graphs $G$ and $H$ are said to be isomorphic iff there exists bijection $f,g$ as defined $f : V(G) \to V(H)$ and $g : E(G) \to E(H)$ such that whenever $g(e) = e'$ then $u$ and $v$ are end points of $e$ iff $f(u)$ and $f(v)$ are end points of $e'$.

Edit: The definition of graph in the book is like this:

A graph $G$ is a triple consisting of a vertex set $V(G)$ and an edge set $E(G)$ and a relation that associates with each edge two vertices not necessarily distinct called end points.

Query 3: Upon reading Bondy Murthy's graph theory book's definiton, I think that in above graph definiton won't it be precise to use "function" and not "relation"?

1

There are 1 best solutions below

0
On

An isomorphism is a bijection (either a bijection $f:V(G) \cup E(G) \to V(H) \cup E(H)$ that sends vertices to vertices and edges to edges, or a pair of bijections $f:V(G) \to V(H)$, $g:E(G) \to E(H)$; these are equivalent). This is correct. There may be more than one isomorphism from $G \to H$. The two graphs are said to be isomorphic if and only if there exists an isomorphism. You are giving a definition of what it means for two graphs to be isomorphic, and the book is giving the definition of an isomorphism.

Their definition for the "relation" is indeed a bit strange. The way they word it, it does sound more like a function taking an edge and returning a set of either one or two vertices (depending on whether the edge is a loop or not).

But really it is better to consider it as a relation between $E(G)$ and $V(G)$. We call this relation "incidence" and it can go both ways. In this case the relation is not a function, because each edge (except loops) is related to two vertices, and each vertex may be related to several edges.