1
$\begingroup$

When working out if two graphs are isomorphic, why can't you use an adjacency matrix and match each pattern of row or column to the other graph's matrix?

The patterns seem to match up and everything works but obviously the answer is wrong; can you not do this?

  • 0
    you could rule them out using eigenvalues, row-sums (column-sums), etc, but there is (currently) no efficient way to prove they are isomorphic, as have mentioned many times. On the other hand, if you are working with small examples to learn, GAP has this package to tell if two matrices are permutation smilar, i.e. their graphs are isomorphic, take a look at this link: http://www.gap-system.org/Manuals/doc/ref/chap71.html#X7D721E3D7AA319F52014-04-24

2 Answers 2

3

The matrices:

$\left(\begin{matrix} 0&0&1&1 \\ 0&0&1&1 \\ 1&1&0&0 \\ 1&1&0&0\end{matrix}\right)$

and:

$\left(\begin{matrix} 0&1&0&1 \\ 1&0&1&0 \\ 0&1&0&1 \\ 1&0&1&0\end{matrix}\right)$

Are incidence matrices for isomorphic graphs.

[As commenter Chris Godsil below has noted, these are adjacency matrices, not incidence matrices, but the same thing applies for incidence matrices.]

  • 0
    As others are telling you, there is no sure-fire efficient way known to decide whether two given graphs are isomorphic. However, for the kind of graph you are likely to see on, say, an undergraduate graph theory exam, you can check number of vertices, number of verices of each degree, etc., possibly ruling out isomorphism. If these tests don't rule it out, you can try to construct an isomorphism, remembering that each vertex in one graph must correspond to a vertex of equal degree in the other. One level more subtle: look at degrees of neighbors of a given vertex.2011-12-29
1

The adjacency matrix itself is not a graph invariant, because it is not invariant under relabeling of the nodes of the graph. Let $B_{n}$ be the set of symmetric, zero-diagonal, $n\times n$ binary matrices. Then the simple graphs on $[n]=\{1,2,...,n\}$ are in a one-to-one correspondence with the elements of $B_n$: take the adjacency matrix of the graph to get its representative in $B_n$. Permutations of the node labels act as follows: for $\pi\in S_{n}$ and $X=(X_{ij})\in B_{n}$, we have $(\pi\cdot X)_{ij}=X_{\pi^{-1}(i),\pi^{-1}(j)}$. The operations $\langle S_{n},\cdot \rangle$ define an equivalence relation on $B_{n}$; and the elements $[X]$ of the quotient $B_{n}/\langle S_{n},\cdot \rangle$ are the desired graph invariants: $G$ and $H$ are isomorphic if and only if their adjacency matrices satisfy $[A(G)]=[A(H)]$.

The problem becomes one of finding a canonical representative for each element of $B_{n}$, or otherwise testing whether any two elements of $B_{n}$ are in the same equivalence class. For instance, one could choose the lexicographically smallest element of the orbit $S_{n}\cdot X$ as the representative of $[X]$ for each equivalence class. The problem with this approach is that the orbit can have size $n!$. Clearly it can be done; but the open question is whether it can be done efficiently. The equivalence-testing problem is not currently known to be NP-hard (and hence NP-complete, since clearly it is in NP); but neither is any polynomial-time algorithm known.