Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a graph $A$ with nodes $p_{1},p_{2},...,p_{n}$, let $\{A^{*}\}$ be the set of all graphs isomorphic to $A$. Consider a graph $Q$ with vertices $a,b,$ and $c$ where there are three edges between $a$ and $b$, one edge between $a$ and $c$, and no edges between $b$ and $c$. Then $Q^{*}\in \{Q^{*}\}$ if and only if it has vertices $d,e,$ and $f$ where there are three edges between two of these nodes, one edge between one of the previous two nodes and the third, and zero edges between the other one of the first two nodes and the third node.

Now, consider the adjacency matrix for a graph $P$. Call it $M(P)$. Then, what conditions may we impose on the relationship between $M(P)$ and $M(A)$ which are necessary and sufficient for saying that $P\in \{A^{*}\}$? Are there results pertaining to this issue? If there are, what are they?

share|improve this question
    
This seems like homework. Are you familiar with the term "Graph Isomorphism"? –  EuYu Nov 2 '12 at 19:07
    
This isn't homework. It's just a thought I have. I am now aware of what a graph isomorphism is, but it does not seem there is a necessary/sufficient theorem pertaining to the relation between the adjacency matrices. –  Jebruho Nov 2 '12 at 19:10
    
I wasn't stating it as a condition. I'm merely pointing out that your set $A^{*}$ is more compactly stated as the set of all graphs isomorphic to $A$. –  EuYu Nov 2 '12 at 19:13
    
I edited it accordingly. Thank you. –  Jebruho Nov 2 '12 at 19:15
add comment

1 Answer

up vote 3 down vote accepted

Two graphs are isomorphic if and only if there is a permutation matrix $P$ relating their adjacency matrices such that $$A = PBP^{-1}$$ where $A$ and $B$ are the adjacency matrices of the two graphs. More compactly, two graphs are isomorphic if and only if their adjacency matrices are similar through a permutation matrix.

To see this, suppose that $\sigma$ is a permutation on the vertices. Let $P$ be the corresponding permutation matrix. Then the adjacency matrices are related by $$b_{i,\ j} = a_{\sigma(i),\ \sigma(j)}$$ Since the entry $b_{i,\ j}$ gives the connectivity condition between vertices $i$ and $j$, this is precisely the isomorphism condition.

Notice that this result has very far reaching consequences. In particular, it allows us to use eigenvalues, trace and other similarity invariants are graph isomorphism invariants.

share|improve this answer
    
Thank you, but is there an efficient way to see if this $P$ exists? –  Jebruho Nov 2 '12 at 19:30
    
@Jebruho That would be essentially equivalent to "is there an easy way of checking if two graphs are isomorphic". Currently it seems to be unknown. See this. –  EuYu Nov 2 '12 at 19:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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