- Graph
- EdgeOrbitsGraph
- NullGraph
- CompleteGraph
- JohnsonGraph
- HammingGraph
- CayleyGraph
- AddEdgeOrbit
- RemoveEdgeOrbit
- AssignVertexNames

This chapter describes the functions used to construct and modify graphs.

`Graph( `

`, `

`, `

`, `

` )`

`Graph( `

`, `

`, `

`, `

`, `

` )`

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, 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 the function `Graph`

returns a graph `gamma` which has as vertex-names (an immutable copy of)

centerline`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

centerline`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 (an immutable copy of) `L`.

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

.

For example, we may use `Graph`

to construct the Petersen graph as follows:

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, 3, 5, 7)( 4, 6, 8, 9,10), ( 2, 4)( 6, 9)( 7,10) ] ), schreierVector := [ -1, 1, 1, 2, 1, 1, 1, 1, 2, 2 ], adjacencies := [ [ 3, 5, 8 ] ], representatives := [ 1 ], names := [ [ 1, 2 ], [ 2, 3 ], [ 3, 4 ], [ 1, 3 ], [ 4, 5 ], [ 2, 4 ], [ 1, 5 ], [ 3, 5 ], [ 1, 4 ], [ 2, 5 ] ] )

The function `Graph`

may be used to construct a graph in GRAPE format
from an adjacency matrix indexadjacency matrix for that graph. For
example, suppose you have an *n* by *n* adjacency matrix *A* for a graph
*gamma*, so that the vertex-set of *gamma* is {1,…,*n*}, and
[*i*,*j*] is an edge of *gamma* if and only if *A*[*i*][*j*]=1. Then the graph
*gamma* in GRAPE-graph format, with associated group the trivial group,
is returned by ```
Graph( Group(()), [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> gamma := Graph( Group(()), [1..3], OnPoints, > function(x,y) return A[x][y]=1; end, > true ); rec( adjacencies := [ [ 2 ], [ 1 ], [ 3 ] ], group := Group(()), isGraph := true, names := [ 1, 2, 3 ], order := 3, representatives := [ 1, 2, 3 ], schreierVector := [ -1, -2, -3 ] )

`EdgeOrbitsGraph( `

`, `

` )`

`EdgeOrbitsGraph( `

`, `

`, `

` )`

This is a common way of constructing a graph in GRAPE.

This function returns the (directed) graph with vertex-set {1,…, *n* }, edge-set ∪_{e ∈ edges } *e*^{G }, and associated
(permutation) group `G`, which must act naturally on {1,…,*n* }.
The parameter `edges` should be a list of edges (lists of length 2 of
vertices), although a singleton edge will be understood as an edge-list
of length 1. The parameter `n` may be omitted, in which case `n` is
taken to be the largest point moved by `G`.

Note that `G` may be the trivial permutation group (`Group( () )`

in
GAP notation), in which case the (directed) edges of `gamma` are
simply those in the list `edges`.

gap> EdgeOrbitsGraph( Group((1,3),(1,2)(3,4)), [[1,2],[4,5]], 5 ); rec( isGraph := true, order := 5, group := Group( [ (1,3), (1,2)(3,4) ] ), schreierVector := [ -1, 2, 1, 2, -2 ], adjacencies := [ [ 2, 4, 5 ], [ ] ], representatives := [ 1, 5 ], isSimple := false )

`NullGraph( `

` )`

`NullGraph( `

`, `

` )`

This function returns the null graph (graph with no edges) with vertex-set
{1,…,*n* }, and associated (permutation) group `G`. The parameter
`n` may be omitted, in which case `n` is taken to be the largest point
moved by `G`.

See also IsNullGraph.

gap> NullGraph( Group( (1,2,3) ), 4 ); rec( isGraph := true, order := 4, group := Group( [ (1,2,3) ] ), schreierVector := [ -1, 1, 1, -2 ], adjacencies := [ [ ], [ ] ], representatives := [ 1, 4 ], isSimple := true )

`CompleteGraph( `

` )`

`CompleteGraph( `

`, `

` )`

`CompleteGraph( `

`, `

`, `

` )`

This function returns the complete graph with vertex-set
{1,…,*n* } and associated (permutation) group `G`. The parameter
`n` may be omitted, in which case `n` is taken to be the largest point
moved by `G`. The optional boolean parameter `mustloops` determines
whether the complete graph has all loops present or no loops (default:
`false`

(no loops)).

See also IsCompleteGraph.

gap> CompleteGraph( Group( (1,2,3), (1,2) ) ); rec( isGraph := true, order := 3, group := Group( [ (1,2,3), (1,2) ] ), schreierVector := [ -1, 1, 1 ], adjacencies := [ [ 2, 3 ] ], representatives := [ 1 ], isSimple := true )

`JohnsonGraph( `

`, `

` )`

Let `n` and `e` be integers, with *n* ≥ *e* ≥ 0. Then this function
returns a graph `gamma` isomorphic to the Johnson graph *J*(*n* ,*e* ).
The vertices (actually the vertex-names) of `gamma` are the `e`-subsets
of {1,…, *n* }, with *x* joined to *y* if and only if |*x* ∩*y*| = *e* −1. The group associated with `gamma` is the image of the symmetric
group *S*_{n } acting on the `e`-subsets of {1,…,*n* }.

gap> JohnsonGraph(5,3); rec( isGraph := true, order := 10, group := Group( [ ( 1, 7,10, 6, 3)( 2, 8, 4, 9, 5), ( 4, 7)( 5, 8)( 6, 9) ] ), schreierVector := [ -1, 1, 1, 2, 1, 1, 1, 2, 1, 1 ], adjacencies := [ [ 2, 3, 4, 5, 7, 8 ] ], representatives := [ 1 ], names := [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 2, 5 ], [ 1, 3, 4 ], [ 1, 3, 5 ], [ 1, 4, 5 ], [ 2, 3, 4 ], [ 2, 3, 5 ], [ 2, 4, 5 ], [ 3, 4, 5 ] ], isSimple := true )

`HammingGraph( `

`, `

` )`

Let `d` and `q` be positive integers. Then this function returns a
graph `gamma` isomorphic to the Hamming graph *H*(*d* ,*q* ). The vertices
(actually the vertex-names) of `gamma` are the `d`-vectors with entries
in {1,…,*q* }, with *x* joined to *y* if and only if *x* and *y*
differ in exactly one co-ordinate (that is, *x* and *y* are at Hamming
distance 1). The group associated with `gamma` is the image of the wreath
product of the symmetric group *S*_{q } with the symmetric group *S*_{d },
in its product action on the vertices.

gap> H:=HammingGraph(3,4); rec( adjacencies := [ [ 2, 3, 4, 5, 9, 13, 17, 33, 49 ] ], group := <permutation group with 8 generators>, isGraph := true, names := [ [ 1, 1, 1 ], [ 1, 1, 2 ], [ 1, 1, 3 ], [ 1, 1, 4 ], [ 1, 2, 1 ], [ 1, 2, 2 ], [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 1 ], [ 1, 3, 2 ], [ 1, 3, 3 ], [ 1, 3, 4 ], [ 1, 4, 1 ], [ 1, 4, 2 ], [ 1, 4, 3 ], [ 1, 4, 4 ], [ 2, 1, 1 ], [ 2, 1, 2 ], [ 2, 1, 3 ], [ 2, 1, 4 ], [ 2, 2, 1 ], [ 2, 2, 2 ], [ 2, 2, 3 ], [ 2, 2, 4 ], [ 2, 3, 1 ], [ 2, 3, 2 ], [ 2, 3, 3 ], [ 2, 3, 4 ], [ 2, 4, 1 ], [ 2, 4, 2 ], [ 2, 4, 3 ], [ 2, 4, 4 ], [ 3, 1, 1 ], [ 3, 1, 2 ], [ 3, 1, 3 ], [ 3, 1, 4 ], [ 3, 2, 1 ], [ 3, 2, 2 ], [ 3, 2, 3 ], [ 3, 2, 4 ], [ 3, 3, 1 ], [ 3, 3, 2 ], [ 3, 3, 3 ], [ 3, 3, 4 ], [ 3, 4, 1 ], [ 3, 4, 2 ], [ 3, 4, 3 ], [ 3, 4, 4 ], [ 4, 1, 1 ], [ 4, 1, 2 ], [ 4, 1, 3 ], [ 4, 1, 4 ], [ 4, 2, 1 ], [ 4, 2, 2 ], [ 4, 2, 3 ], [ 4, 2, 4 ], [ 4, 3, 1 ], [ 4, 3, 2 ], [ 4, 3, 3 ], [ 4, 3, 4 ], [ 4, 4, 1 ], [ 4, 4, 2 ], [ 4, 4, 3 ], [ 4, 4, 4 ] ], order := 64, representatives := [ 1 ], schreierVector := [ -1, 5, 5, 5, 3, 5, 5, 5, 3, 5, 5, 5, 3, 5, 5, 5, 1, 5, 5, 5, 3, 5, 5, 5, 3, 5, 5, 5, 3, 5, 5, 5, 1, 5, 5, 5, 3, 5, 5, 5, 3, 5, 5, 5, 3, 5, 5, 5, 1, 5, 5, 5, 3, 5, 5, 5, 3, 5, 5, 5, 3, 5, 5, 5 ] ) gap> GlobalParameters(H); [ [ 0, 0, 9 ], [ 1, 2, 6 ], [ 2, 4, 3 ], [ 3, 6, 0 ] ]

`CayleyGraph( `

` )`

`CayleyGraph( `

`, `

` )`

`CayleyGraph( `

`, `

`, `

` )`

Given a group `G` and a generating list `gens` for `G`, ```
CayleyGraph(
```

`G``, `

`gens`` )`

returns a Cayley graph for `G` with respect to `gens`.
The generating list `gens` is optional, and if omitted, then `gens` is
taken to be `GeneratorsOfGroup( `

`G`` )`

. The boolean argument `undirected`
is also optional, and if `undirected`=`true`

(the default), then the
returned graph is undirected (as if `gens` was closed under inversion,
whether or not it is).

The Cayley graph `caygraph` which is returned is defined as follows:
the vertices (actually the vertex-names) of `caygraph` are the elements
of `G`; if `undirected`=`true`

(the default) then vertices *x*,*y* are
joined by an edge if and only if there is a *g* in the list `gens` with
*y*=*gx* or *y*=*g*^{−1}*x*; if `undirected`=`false`

then [*x*,*y*] is an edge
if and only if there is a *g* in `gens` with *y*=*gx*.

The permutation group `caygraph``.group`

associated with `caygraph` is
the image of `G` acting in its right regular representation.

**Note** It is not checked whether `G` is actually generated by `gens`.
However, even if `G` is not generated by `gens`, the function still
works as described above (as long as `gens` is contained in `G`), but
returns a ``Cayley graph'' which is not connected.

gap> C:=CayleyGraph(SymmetricGroup(4),[(1,2),(2,3),(3,4)]); rec( isGraph := true, order := 24, group := Group( [ ( 1,10,17,19)( 2, 9,18,20)( 3,12,14,21)( 4,11,13,22)( 5, 7,16,23) ( 6, 8,15,24), ( 1, 7)( 2, 8)( 3, 9)( 4,10)( 5,11)( 6,12)(13,15) (14,16)(17,18)(19,21)(20,22)(23,24) ] ), schreierVector := [ -1, 1, 1, 2, 2, 1, 2, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2 ], adjacencies := [ [ 2, 3, 7 ] ], representatives := [ 1 ], names := [ (), (3,4), (2,3), (2,3,4), (2,4,3), (2,4), (1,2), (1,2)(3,4), (1,2,3), (1,2,3,4), (1,2,4,3), (1,2,4), (1,3,2), (1,3,4,2), (1,3), (1,3,4), (1,3)(2,4), (1,3,2,4), (1,4,3,2), (1,4,2), (1,4,3), (1,4), (1,4,2,3), (1,4)(2,3) ], isSimple := true ) gap> Girth(C); 4 gap> Diameter(C); 6

`AddEdgeOrbit( `

`, `

` )`

`AddEdgeOrbit( `

`, `

`, `

` )`

This procedure adds the orbit of `e` under `gamma``.group`

to the
edge-set of the graph `gamma`. The parameter `e` must be a sequence of
length 2 of vertices of `gamma`. If the optional third parameter `H` is
given then it is assumed that `e``[2]`

has the same orbit under `H` as
it does under the stabilizer in `gamma``.group`

of `e``[1]`

, and this
knowledge can speed up the procedure.

Note that if `gamma``.group`

is trivial then this procedure simply adds the
single (directed) edge `e` to `gamma`.

See also RemoveEdgeOrbit.

gap> gamma := NullGraph( Group( (1,3), (1,2)(3,4) ) );; gap> AddEdgeOrbit( gamma, [4,3] ); gap> gamma; rec( isGraph := true, order := 4, group := Group( [ (1,3), (1,2)(3,4) ] ), schreierVector := [ -1, 2, 1, 2 ], adjacencies := [ [ 2, 4 ] ], representatives := [ 1 ], isSimple := true ) gap> GlobalParameters(gamma); [ [ 0, 0, 2 ], [ 1, 0, 1 ], [ 2, 0, 0 ] ]

`RemoveEdgeOrbit( `

`, `

` )`

`RemoveEdgeOrbit( `

`, `

`, `

` )`

This procedure removes the orbit of `e` under `gamma``.group`

from the
edge-set of the graph `gamma`. The parameter `e` must be a sequence of
length 2 of vertices of `gamma`, but if `e` is not an edge of `gamma`
then this procedure has no effect. If the optional third parameter `H`
is given then it is assumed that `e``[2]`

has the same orbit under `H`
as it does under the stabilizer in `gamma``.group`

of `e``[1]`

, and
this knowledge can speed up the procedure.

See also AddEdgeOrbit.

gap> gamma := CompleteGraph( Group( (1,3), (1,2)(3,4) ) );; gap> RemoveEdgeOrbit( gamma, [1,3] ); gap> gamma; rec( isGraph := true, order := 4, group := Group( [ (1,3), (1,2)(3,4) ] ), schreierVector := [ -1, 2, 1, 2 ], adjacencies := [ [ 2, 4 ] ], representatives := [ 1 ], isSimple := true ) gap> GlobalParameters(gamma); [ [ 0, 0, 2 ], [ 1, 0, 1 ], [ 2, 0, 0 ] ]

`AssignVertexNames( `

`, `

` )`

This procedure allows the user to give new names for the vertices of
`gamma`, by specifying a list `names` (of length `gamma``.order`

) of
vertex-names for the vertices of `gamma`, such that `names``[`

`i``]`

contains the user's name for the `i`-th vertex of `gamma`.

An immutable copy of `names` is assigned to `gamma``.names`

.

See also VertexNames and VertexName.

gap> gamma := NullGraph( Group(()), 3 ); rec( isGraph := true, order := 3, group := Group( [ () ] ), schreierVector := [ -1, -2, -3 ], adjacencies := [ [ ], [ ], [ ] ], representatives := [ 1, 2, 3 ], isSimple := true ) gap> AssignVertexNames( gamma, ["a","b","c"] ); gap> gamma; rec( isGraph := true, order := 3, group := Group( [ () ] ), schreierVector := [ -1, -2, -3 ], adjacencies := [ [ ], [ ], [ ] ], representatives := [ 1, 2, 3 ], isSimple := true, names := [ "a", "b", "c" ] )

[Up] [Previous] [Next] [Index]

grape manual

June 2018