> < ^ Date: Thu, 04 Oct 2001 17:04:10 +0200
> < ^ From: Dmitrii Pasechnik <d.pasechnik@twi.tudelft.nl >
< ^ Subject: Re: GRAPE and Automorphisms of edge-colored graphs

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...


> < [top]