I have nodes a, b , c,d,N, and e in an adjacency matrix. If I follow the order as a,b,c,d,N,and,e , I get 100010(the question does not matter because I'm asking about the order) for b.But if I follow the order a,b,c,N,d,and e, I get 100100 which was done by my TA in the class. Does the order really matter? If so then is there a way to find order from the adjacency graphs?

  • 5
    $\begingroup$ Of course, if you change the order, your adjacency matrix is very likely to change, but the graph does not change (it is the same graph). You may read about isomorphism in order to understand the difference between graphs and their representation and how they can be used interchangeably. $\endgroup$ – orezvani May 10 '16 at 3:13
  • $\begingroup$ What do you mean by "order" here? How do you arrive at 100010 and 100100? $\endgroup$ – Rick Decker May 11 '16 at 20:24

Let $f$ be an isomorphism from graph $G$ to graph $G'$ which takes vertex $v_i$ to vertex $v_i'$. Let $A$ and $A'$ be the adjacency matrix of $G$ and $G'$, respectively. If the rows and columns of $A$ are in the order $v_1,\ldots,v_n$, and the rows and columns of $A'$ follow the same order $v_1', \ldots, v_n'$, then it can be seen that $A=A'$.

If $f$ is an isomorphism from $G$ to itself, then $f$ is called an automorphism of $G$. Thus, $f$ is a permutation of $V(G)$ which maps edges to edges and nonedges to nonedges. If we permute the rows of the adjacency matrix $A$ by $f$, and if we apply the same permutation to the columns of $A$, we get back the same matrix $A$. Equivalently, a permutation $f$ of $V(G)$ is an automorphism of $G$ if and only if the permutation matrix $P$ corresponding to $f$ satisfies the equation $P^{-1}AP=A$. Recall that premultiplying a matrix $A$ effects row operations/permutations and postmultiplication effects column permutations.

So, graphs with the same structure (i.e. isomorphic graphs) have the same adjacency matrix (up to a permutation of the rows and columns - here, the same permutation must be applied to both the rows and the columns). The graph invariants which we study are the same for isomorphic graphs and so the ordering of vertices you choose for the adjacency matrix shouldn't matter.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.