GAP Instructional Material
GAP code is shown like this .
[Press ?? to see GAP output]
You can also choose to see a page showing ALL GAP output.
Graph Theory using the GRAPE package
Before you can use GRAPE, you will need to load the GRAPE package into GAP (assuming GRAPE has
been installed on your computer).
RequirePackage("grape");
??
Defining and Modifying Graphs
We can define any graph by its automorphism group G, a list of elements L and an
adjacency matrix A:
A := [[0,1,0],[1,0,0],[0,0,1]];;
G := Group( (1,2) );;
Graph( G, [1..3], OnPoints, function(x,y) return A[x][y]=1; end, true );
??
We can also define the Peterson Graph using this command
Petersen := Graph( SymmetricGroup(5), [[1,2]], OnSets, function(x,y) return
Intersection(x,y)=[]; end );
??
GRAPE stores each graph as a record with 6 components. The exact structure of this is not vital for using
GRAPE, but it is worth noting that representatives stores the orbit representatives of the
action of group , and adjacencies stores the set of vertices adjacent to these
representatives.
We can also define particular types of graph using specialised commands. For example, the Null Graph
with no edges
NullGraph( Group( (1,2,3) ), 4);
??
where the group defines the permutation group associated with the graph, and the optional second
argument defines the order (if this is omitted GRAPE will use the size of the largest orbit of the group).
Note that, despite two null graphs of the same order being visibly identical, they may be defined with
different permutation groups. However
IsIsomorphicGraph(NullGraph(Group(()), 4), NullGraph(Group((1,2,3)),
4);
??
We can also define the complete graph
CompleteGraph( Group(1,2,3), (1,2) ) );
??
where the first argument again defines the group, and the (optional) second argument specifies the order
of the graph. A further third option can be set to true to include loops (edges from a point
to itself):
CompleteGraph(Group((1,2,3),(1,2)), 3, true);
??
the result being that the graph is no longer simple. A useful way of defining graphs:
EdgeOrbitsGraph( Group((1,3),(1,2)(3,4)), [[1,2],[4,5]], 5);
??
which returns the graph with the specified permutation group and edgeset those specified in the second
argument and all edges under the action of the group. The third argument is again optional. We can also
use the trivial permutation group to define a graph containing only the edges specified in the second
argument:
gamma := EdgeOrbitsGraph( Group(()), [[1,2],[2,3],[3,1]], 3);
??
DirectedEdges(gamma);
??
Lets now add some edges to our graph. We use AddEdgeOrbit to do this, which will add
our edge and its orbits under the graph's permutation group. In this case, our permutation group is trivial
so we will merely add the specified edges.
AddEdgeOrbit(gamma, [2,1]); gamma;
??
We can also remove the edge again
RemoveEdgeOrbit(gamma, [2,1]); gamma;
??
Now let us define another graph with nontrivial permutation group, and see what happens when we add an
edge:
delta := NullGraph( Group( (1,3), (1,2)(3,4) ) );; AddEdgeOrbit (delta,
[4,3]); DirectedEdges(delta);
??
Now we can also define a new graph, based on a graph we already have but with a different permutation
group
NewGroupGraph(Group((1,2)), delta);
??
We also have two other types of graph with shortcut definitions: the Cayley Graph of a group G
CayleyGraph(SymmetricGroup(4));
??
which has the optional second argument specifying generators of G (otherwise it uses
GeneratorsOfGroup(G) ), and an optional third argument specifying whether the graph is
directed or not (default = true ).The Johnson Graph J(n,e) can also be defined
JohnsonGraph(5,3);
??
Note here the vertices have 'names'. In this case the names are lists of numbers, and the Johnson graph
J(n,e) has vertices the esubsets of {1,...,n}, and x connected to y if
and only if their intersection has size e  1. We can, however, assign vertex names to any graph:
gamma := NullGraph(Group(()), 3);; AssignVertexNames( gamma,
["a","b","c"] ); gamma;
??
Inspecting graphs, vertices and edges
We will use the Johnson Graph J(4,2) to demonstrate a few commands we can use to inspect
graphs.
J42 := JohnsonGraph(4,2);
??
First of all a few needing no explanation
IsGraph(J42);
??
OrderGraph(J42);
??
Vertices(J42);
??
IsSimpleGraph(J42);
??
IsConnectedGraph(J42);
??
IsRegularGraph(J42);
??
The girth of a graph is the length of a shortest cycle. Trees and forests will return 1.
Girth(J42);
??
The diameter is the maximum (directed) distance between two vertices. If the graph is not connected it will
return 1.
Diameter(J42);
??
We can check whether a particular edge is in the graph
IsEdge(J42, [ 1, 2 ]);
??
and we have already seen DirectedEdges gives us a list of all directed edges. If our graph is
simple we can also use
UndirectedEdges(J42);
??
We can find which vertices are adjacent to a given vertex. A vertex w is adjacent to v if and
only if [v,w] is an edge.
Adjacency(J42, 1);
??
and also the (minimum) distance between two points
Distance(J42, 1, 6);
??
or even sets of points
Distance(J42, [1], [5,6]);
??
If we wish to know which points are at a given (minimal) distance, we can use
DistanceSet(J42, 2, 1);
??
and we can also use this on sets of points too
DistanceSet(J42, 1, [1,6]);
??
We can also produce a list of lists of elements, the ith element being the set of vertices at a distance
i1 from our specified vertex or vertex set.
Layers(J42, 6);
??
We can check whether a vertex is in a graph
IsVertex(J42,7);
??
and for a vertex in the graph, we can also find out its name (if it has one)
VertexName(J42, 6);
??
or use the following command to give the names of all the vertices
VertexNames(J42);
??
The degree of a vertex v can be obtained using the following
VertexDegree(J42, 2);
??
and again we can get a set of all vertex degrees using the following, although note that this will only show
each degree value once
VertexDegrees(J42);
??
A loop is an edge of the form [x, x]. GRAPE regards graphs with loops not to be simple, but we
can be more specific
IsLoopy(J42);
??
Bipartite graphs and connectivity
On a graph that is simple we may check whether it can be expressed as the disjoint union of two sets, with
edges only between the sets. That is, whether it is bipartite
IsBipartite(J42);
??
So how can we colour this graph? We can get a proper vertexcolouring using the following. The output
is a list indexed by the vertices of the graph.
VertexColouring(J42);
??
So it can be coloured using 3 colours. However, we can use the following argument to construct a bipartite
graph from our graph J42 :
J42BPD := BipartiteDouble(J42);
??
IsBipartite(J42BPD);
??
a result which is confirmed if we try vertex colouring
VertexColouring(J42BPD);
??
Alternatively, we can even get GRAPE to tell us how to partition our newlyformed bipartite graph
Bicomponents(J42BPD);
??
but if we try that on a nonbipartite graph it will return an empty list. On a nonconnected graph it will of
course be nonunique:
null4 := NullGraph(Group((1,2)), 4);; Bicomponents(null4);
??
Lets add an edge to null4 . We defined it with a group genertaed by (1,2) so adding [1,2]
will also add [2,1] and keep the graph simple.
AddEdgeOrbit(null4, [1,2]); Bicomponents(null4);
??
We can also find the connected components of the graph null4
ConnectedComponents(null4);
??
Associated with bipartite graphs is the notion of an independent set: a set of vertices no two of which are
joined by an edge
IndependentSet(J42BPD);
??
although we can also specify a second argument to contain specific vertices, and a third to exclude specific
vertices
IndependentSet(J42BPD, [7], [8,9,10]);
??
Constructing new graphs from old
The induced subgraph of a graph, given vertex list V is the graph containing only those vertices in
V, and any edges between two elements of V that were in the original graph.
squaregraph := InducedSubgraph(J42, [2,3,4,5]);
??
UndirectedEdges(squaregraph);
??
We can also construct a subgraph of a graph gamma on a (set of) vertices and all those vertices
within a certain distance of the specified vertex/vertices
DistanceSetInduced(J42, [0,1], [1] );
??
and also the complement of a graph  two points lie on an edge in the new graph if and only they they did
not lie on an edge in the old graph
ComplementGraph(J42);
??
ConnectedComponents(last);
??
We can 'switch' edges and vertices to form the edge graph of a graph gamma. Here the edges in the
new graph occur precisely when two edges in the old graph meet at a vertex.
EdgeGraph(J42);
??
Supposing we have a nonsimple graph, and we wish to change all directed edges into undirected edges
(effectively making the graph simple), then we can use
gamma := EdgeOrbitsGraph( Group ((1,2,3,4)), [1,2] );
??
UnderlyingGraph(gamma);
??
Finally, supposing we want to find the complete subgraphs contained within a graph. Lets define a bigger
graph, the Johnson graph J(6,2):
J62 := JohnsonGraph(6,2);
??
CompleteSubgraphs(J62);
??
It returns the maximal complete subgraphs it can find. Supposing we want a particular size of complete
subgraph, then we can specify an extra parameter
CompleteSubgraphs(J62, 3);
??
Of course there are others, e.g. [1,2,4] , but this method makes use of the automorphism
group associated with our graph. If we want to find all the complete subgraphs, we could try redefining
the graph to have trivial group:
gamma :=
NewGroupGraph(Group(()),J62);; CompleteSubgraphs(gamma);
??
Specifying we only want those of size 3 would make this list even longer.
Robert Brignall May 2004
