> < ^ From:

< ^ Subject:

Dear Forum,

On Thu, Oct 04, 2001 at 10:21:55AM +0200, Gregoire Misguich wrote:

> I am using GAP4.2 and the share package GRAPE to compute

> automorphism groups of graphs given by their incidence matrix.

>

> My question is the following: is it possible to compute in a similar way

> the automorphism group of an edge-colored graph (i.e. incidence matrix

> with integers, not only 0 and 1) ?

>

Create the edge-graph (GAP/Grape function EdgeGraph)

of your graph; then the vertices of the new graphs

are coloured, instead of the edges.

One can specify a partition of the vertices to be preserved by the

automorphisms you want to compute (the 2nd parameter of AutGroupGraph)

So this will give you what you need for the connected

graphs with more than 4 vertices

(because edge graphs of two nonisomorphic connected graphs are not isomorphic, unless

one is K_3 and the other is K_{1,3})

----------------

Alternatively, but almost certainly with much less efficiency, one can compute

automorphism groups for each colour, and then take the intersection.

----------------

The reason for all these workarounds needed

is that Nauty, the external routine used to compute automorphims,

work with graphs stored as 0-1 matrices, one 0/1 per bit...

HTH,

Dmitrii

http://ssor.twi.tudelft.nl/~dima/

> < [top]