0
$\begingroup$

Based on the definition of Isomorphism i.e two graphs are isomorphic if there exists a Bijection between Vertices sets and Edge sets of the two graphs. Since a graph can be represented as a Matrix with rows and columns matrix representing the vertices set, can this matrix representation be used to prove if two graphs are Isomorphic ?

Thus if two matrices are equal then the graphs corresponding to those matrices are Isomorphic. Is this statement correct ? If not can you provide the correct statement.

$\endgroup$
1
  • 1
    $\begingroup$ If two matrices are equal, then corresponding graphs are isomorphic: this is true. However this condition is not necessary, there could be isomorphic graphs represented by different matrices. $\endgroup$
    – Crostul
    Nov 9, 2020 at 7:36

1 Answer 1

1
$\begingroup$

Thus if two matrices are equal then the graphs corresponding to those matrices are Isomorphic.

This statement is true. However, adjacency matrix and incidence matrix can be used in order to verify an isomorphism, rather than finding one. This is because when we write an adjacency matrix of two graphs that are isomorphic, if the ordering of vertices in matrix representations is not the same, then we probably get a different matrix. But, if we have an isomorphism between two graphs $G$ and $H$, say $\phi: G \to H$, with $V(G) = \{v_1,v_2,...,v_n\}$ and $V(H) = \{u_1, u_2,...,u_n\}$ then the ordering in adjacency matrices of these graphs should be like $(v_1,...,v_n)$ and $(\phi(v_1),...,\phi(v_n))$. Here, note that there might be more than one isomorphism and we may get the same matrices with different orderings.

In summary, if we can define a function $\phi: G \to H$ and suspecting that $\phi$ is an isomorphism, then we can verify it by comparing the matrices with orderings $(v_1,...,v_n)$ and $(\phi(v_1),...,\phi(v_n))$. If this is the case, matrices being the same proves that $\phi$ is an isomorphism.

$\endgroup$
1
  • $\begingroup$ Similarly for the incidence matrix, we allow permutations of rows and columns which is trivial because isomorphism is about unlabelled graphs. Detailed examples can be found in SO although obviously that is off-topic for SO. $\endgroup$
    – An5Drama
    Jan 12 at 5:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .