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?

  • 1
    The adjacency matrix is different depending on how you order the nodes. Obviously, if your graphs are isomorphic and you order the nodes properly, you'll get the same matrix, but if you don't know whether they are isomorphic, different orders of nodes give different matrices.2011-12-28
  • 1
    if you consider the adjacency matrix up to conjugation by a permutation, it is an invariant (ie relabeling of vertices).2011-12-28
  • 0
    There is nothing wrong with the approach in principle. But one has to test all permutations. However, easily computed matrix invariants can be used to rule out isomorphism in many cases.2011-12-28
  • 0
    Is there a easy way to work out if they are isomorphic? Can you show me or link me to the "easily computed matrix invariants"? I'm studying for my exams and am having troubling identifying which vertex is which when they are isomorphic.2011-12-28
  • 0
    There is a huge literature. A lot of work has been done with eigenvalues.2011-12-28
  • 1
    There are plenty of matrix invariants, but they don't do a good job of proving isomorphism, just ruling out isomorphism. For example, the characteristic polynomial of the adjacency matrix is an invariant, but it isn't "faithful." That is, if $G$ and $G'$ are graphs, then the characteristic polynomial of their adjacencies will be the same if they are isomorphic, but if the polynomials are the same, they are not necessarily isomorphic.2011-12-28
  • 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
    Can you explain more please? So for these two graphs how can you use the incidence matrices to show they are isomorphic? - http://cl.ly/3s2Y2F231X0X3I1746282011-12-28
  • 0
    My point is that the incidence matrices are not the same for isomorphic graphs - which means that it is not an invariant.2011-12-28
  • 0
    I see, is there an easy way to work out if they are isomorphic and easy way to state which vertex on graph G belongs to vertex on graph H?2011-12-28
  • 0
    Surprisingly, that's an open question. Graph isomorphism is in NP, but nobody knows whether it's P or whether it's NP-complete.2011-12-28
  • 0
    According to Wikipedia, there is no known polynomial-time solution, but I found a link to an article that claims a polynomial-time algorithm. http://www.dharwadker.org/tevet/isomorphism/ It's the internet, so there's no telling if it is right or wrong :)2011-12-28
  • 4
    These are not incidence matrices, they are adjacency matrices. (The incidence matrix has rows indexed by vertices and columns indexed by edges, so usually it is not square.2011-12-29
  • 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.