Let’s start with the first one.
In the picture below, you will see the two actual graphs that I will create and execute Traces or nauty by the dreadnaut.
Now, it’s the time to feed it to the dreadnaut and get the result! And this is how you should do it.
So let’s break it down a little bit, to make things clear. I used Traces “At”, in “c -a V=0” basically means we are labeling graph and limiting the output to get a specific result, “n=12 g” means we have a graph with 12 vertices and then defining the graph, “x” means executed and in case for saving the result we use”@”, then “##” means compare the graphs.
Here, we see that these two graphs came out to be isomorphism “identical” and the next line shows us the bijection vertices which is literally the proof of isomorphism. 🙂
And that’s it! we just proved the first step!
There is another example in here:
Now, let’s run it on the dreadnaut with traces again.
As you see, it detected ” h ” as an isomorphic to ” h’ “.
Now, the bijection vertices are “0-5”, “1-4”, “2-3”, “3-2”, “4-1”, “5-0”.
Some notions
When we work with graphs we might need to add labels on edges or vertices. Labeling means assigning labels (that could be integers, alphabets or anything that you want) to edges and/or vertices of a graph.
As far as I know, you can label vertices and can have a canonical labeled graph and executed with both nauty and traces. Also, you can label as many vertices as you want to, however, I could not find any information about labeling the edges itself.
Hence, you will have some utilities to work with labeling through commands such as:
“labelg”: Canonically label graphs.
“biplabg”: Label bipartite graphs so the colour classes are contiguous.
“-l”: Shows you Canonically label output graphs.
“$=#”: Set label of first vertex (default 0) it also could be the alphabet not only numbers.
And there would be more as you work with it.
Some Mathematical notions:
A canonical labeling that also called a canonical form, of a graph G is a graph G’ which is isomorphic to G and which represents the whole isomorphism class of G (Piperno 2011).
A bipartite graph, also called a bigraph, is a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent.
So, let’s go and do a test of automorphism with labeled vertices graph.
Consider D = { {1, 2, 4}, {1, 3}, {2, 3, 4} }. We are going to prove that D is isomorphism to labeled G(D) so that the varieties of D correspond to vertices 1–4, while the blocks correspond to vertices 5–7. This time we will do it with the sparse version of nauty.
So now, let’s see the result on dreadnaut.
Up there where you see “$=1 As” means we are labeling vertices starting at 1, and also using sparse mode.
Then this “f=[1:4]” means fix the varieties setwise in the graph. “cx” here is where we run nauty.
Now, where you see “(2 4), (1 3) (5 7)” thoes are group generators. With “o” we display the orbits. With “b” we display the canonical labelling and the result will be the vertices in canonical order and the relabelled graph.