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 am having a little trouble understanding some results from a program i wrote. I think i have the correct results but i need to understand the theory behind it a little more (i am a programmer, not mathematician).

My program generates symmetric k-regular graphs (single undirected edges). It generates an adjacency matrix and i take that adjacency matrix and find it's canonical isomorph. I compare the canonical isomorph to the list of all previous ones i have found to determine it if's a new k-regular graph.

So here is an example and i think it is correct but i just need to understand the result a little more.

n = 6
k = 2

Adjacency Matrix 1:

0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 1
0 0 0 1 0 1
0 0 0 1 1 0


Canonical Isomorph:
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 1
0 0 0 1 0 1
0 0 0 1 1 0

The relabeling Label:
0 1 2 3 4 5
(which is the identity)

Adjacency Matrix 2:
0 1 1 0 0 0
1 0 0 1 0 0
1 0 0 0 1 0
0 1 0 0 0 1
0 0 1 0 0 1
0 0 0 1 1 0

Canonical Isomorph:
0 1 1 0 0 0
1 0 0 0 1 0
1 0 0 0 0 1
0 0 0 0 1 1
0 1 0 1 0 0
0 0 1 1 0 0
Relabeling:
0 1 2 5 3 4

Does this look correct? Labeling means each vertex is labeled from 0-5.

share|improve this question
    
What do you understand by "canonical isomorph"? –  Rasmus Oct 2 '10 at 16:48
add comment

1 Answer 1

up vote 1 down vote accepted

Looks okay to me. The first graph is two disjoint copies of C_3 whereas the second graph is C_6. They are not isomorphic and they receive a different canonical label (which is correct). And there's no other 2-regular simple graphs on 6 vertices. The permutation listed is applied to the rows and columns of the matrix.

Is there anything more specific you want to clarify?

You could also compare your output with that of nauty. It also has a function geng that can be used to generate graphs with various properties.

share|improve this answer
    
yeah, i used nauty to generate the canonical isomorph and the labelling. –  gprime Oct 3 '10 at 0:05
    
So i guess i did everything correct. I was worried because it was too easy... –  gprime Oct 3 '10 at 0:05
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.