# Does Sage keep the order of vertices in a graph and it's group or scramble them? For me it sometime scrambles them.

I use the Sage automorphism_group function to find the group that leaves an adjacency matric, say C, invariant under a similarity transformation. But sometimes it seems the results are for matrices on a vertex space that is not the same as the original, but is reordered.

A simple example on a 3-vertex graph: o--o--o.

with index order               1  0  2


 [0 1 1]
[1 0 0]
[1 0 0]


The group is the identity and a reflection about the center vertex:

[1 0 0]       [0 1 0]
[0 1 0]  and  [1 0 0] = R
[0 0 1]       [0 0 1]


I would have expected the reflection to be,

[1 0 0]
[0 0 1]
[0 1 0],


but R is what Sage gives.

Sure enough, RCR^-1 gives the following,

[0 1 0]
[1 0 1]
[0 1 0]


which is not the original C matrix. However the R transformation leaves the matrix

[0 0 1]
[0 0 1] = C'
[1 1 0]


invariant. The last matrix is the C matrix where the vertices are indexed in reverse order.

Does Sage have some canonical way it orders the vertices in graphs and groups?

A bit more info, maybe. The order of the irreducible representation table seems to give a hint. If the trivial representation is the first row (which it is for some graphs), it appears (from a few tests) that the vertices retain their original order to align with C. If the trivial representation is the last row then the matrix C' is the adjacency matrix (suggesting a reordering of the vertices). I have no idea why this should be related if it is.

Bottom line for me is I cannot apply any matrices from the group that come from the matrix() method to C or other objects in my original vertex space since they are ordered differently. I don't see how to find the vertex order sage uses. Any help or insight appreciated.

edit retag close merge delete

Sort by » oldest newest most voted
sage: G = graphs.PathGraph(3)
sage: G
Path Graph: Graph on 3 vertices
sage: H = G.automorphism_group()
sage: H
Permutation Group with generators [(2,3)]


So that sounds like not necessarily connected, especially since GAP (our group engine) notation starts counting at one, but our graphs (like most Python stuff) starts at zero. That said,

sage: G.automorphism_group??


could give you some clues. Sorry. In this case, a group is just a group. Is there a theorem that says there should be a connection? It's not as if we are giving a subgroup of the easy representation of the permutation group on all vertices; I can't find a matrix() method for G or H.

more

Thanks for the answer Kcrisman. I looked at automorphism_group?? and I may have found the answer. There is a keyword option 'translation' which gives a dict for mapping from vertices of the graph (dict keys using python indexing from 0) to the permutation elements (1,2,3,...) which must be positive integers. When I printed the dict for a simple graph the 0th vertex is mapped to the last integer, the others appear to be mapped to the same integer as the python index (since those are positive and non-zero). Does this sound right? I will be experimenting with this "reordering" and I'll let you know if it worked. Thanks, you might have solved another group-graph puzzle for me.

( 2012-09-12 14:40:10 +0200 )edit

yes, typically the mapping from a graph with vertices 0..n-1 in Sage in situations like these is done by making vertex 0 vertex n. That way most of the vertices have the same numbers.

( 2012-09-15 01:40:19 +0200 )edit

I found there is a translation table keyword option for the automorphism_group() call which returns a table showing which vertex indices (which go from 0 to n-1, where n is the group order) match the cycle labels (which go from 1 to n since they must all be > 0 integers). The table tells you how Sage is internally ordering the vertices so you can match up the output group matrices with your original vertex vector space. This helps align your adjacency matrix with the outputs from the automorphism_group method and other items calculated from that group like the matrices.

Thanks to krisman for suggesting I look at D.automorphism_group?? info.

more

I meant kcrisman, sorry.

( 2012-09-12 19:44:44 +0200 )edit