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.

I've been given the following adjacency matrix:

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

and I need to prove that it is a self complementary graph. All this must be done by hand so I found the complementary graph but I don't know how to continue.

The graph and its complement

Do I need to solve

$$Ax=b$$

or

$$x^{t}Ax=b$$

is $x$ a matrix defined by 8 columns and 8 rows?

share|improve this question
1  
you want $x$ to be a permutation matrix, and that $x^T A x = J-I-A$. THe LHS is the isomorphism under permutation, and the RHS is the complement of $A$, where $J$ is the all 1's matrix, and $I$ is the identity matrix (since there are no self loops). –  Calvin Lin Jun 21 '13 at 15:35
    
x is then a matrix with 8 columns and 8 rows? –  Cristian Eduardo Lehuede Lyon Jun 21 '13 at 17:54
add comment

1 Answer 1

The blue graph has the big square 2-4-6-8 with little triangles 2-3-4, 4-5,6, 6-7-8, and 8-1-2, and also the little triangle vertices which are opposite relative to the big square are joined, i.e. 1-5 and 3-7.

The red graph has a similar description: there is a big square 1-3-5-7, and triangles 1-6-3, 3-8-5, 5-2-7, and 7-4-2, and also the triangle vertices which are opposite relative to the big square are joined, i.e. 2-6 and 8-4.

This means one can set up an isomorphism by corresponding the vertices as

Blue: $[1,2,3,4,5,6,7,8],$

Red: $[4,1,6,3,8,5,2,7].$

share|improve this answer
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.