63.2 Graph

Graph( G, L, act, rel )
Graph( G, L, act, rel, invt )

This is the most general and useful way of constructing a graph in GRAPE.

First suppose that the optional boolean parameter invt is unbound or has value false. Then L should be a list of elements of a set S on which the group G acts (operates in GAP language), with the action given by the function act. The parameter rel should be a boolean function defining a G-invariant relation on S (so that for g in G, x,y in S, <rel>(x,y) if and only if <rel>(<act>(x,g),<act>(y,g))). Then function Graph returns a graph gamma which has as vertex names Concatenation( Orbits( G, L, act ) ) (the concatenation of the distinct orbits of the elements in L under G), and for vertices v,w of gamma, [v,w] is an edge if and only if rel( VertexName( gamma, v ), VertexName( gamma, w ) )

Now if the parameter invt exists and has value true, then it is assumed that L is invariant under G with respect to action act. Then the function Graph behaves as above, except that the vertex names of gamma become (a copy of) L.

The group associated with the graph gamma returned is the image of G acting via act on gamma.names.

For example, suppose you have an nx n adjacency matrix A for a graph X, so that the vertices of X are {1,ldots,n}, and [i,j] is an edge of X if and only if A[i][j]=1. Suppose also that G le Aut (X) (G may be trivial). Then you can make a GRAPE graph isomorphic to X via Graph( G, [1..n], OnPoints, function(x,y) return A[x][y]=1; end, true );

    gap> A := [[0,1,0],[1,0,0],[0,0,1]];
    [ [ 0, 1, 0 ], [ 1, 0, 0 ], [ 0, 0, 1 ] ]
    gap> G := Group( (1,2) );
    Group( (1,2) )
    gap> Graph( G, [1..3], OnPoints,
    >           function(x,y) return A[x][y]=1; end,
    >           true );
    rec(
      isGraph := true,
      order := 3,
      group := Group( (1,2) ),
      schreierVector := [ -1, 1, -2 ],
      adjacencies := [ [ 2 ], [ 3 ] ],
      representatives := [ 1, 3 ],
      names := [ 1 .. 3 ] ) 

We now construct the Petersen graph.

    gap> Petersen := Graph( SymmetricGroup(5), [[1,2]], OnSets,
    >                 function(x,y) return Intersection(x,y)=[]; end );
    rec(
      isGraph := true,
      order := 10,
      group := Group( ( 1, 2)( 6, 8)( 7, 9), ( 1, 3)( 4, 8)( 5, 9),
        ( 2, 4)( 3, 6)( 9,10), ( 2, 5)( 3, 7)( 8,10) ),
      schreierVector := [ -1, 1, 2, 3, 4, 3, 4, 2, 2, 4 ],
      adjacencies := [ [ 8, 9, 10 ] ],
      representatives := [ 1 ],
      names := [ [ 1, 2 ], [ 2, 5 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ],
          [ 1, 3 ], [ 1, 4 ], [ 3, 5 ], [ 4, 5 ], [ 3, 4 ] ] ) 

Previous Up Top Next
Index