# Canonical Isomorphic Graphs

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

 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.

-
What do you understand by "canonical isomorph"? –  Rasmus Oct 2 '10 at 16:48

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.

-
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