GAP Instructional Material

Return to Index

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 edge-set 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]);

We can also remove the edge again

RemoveEdgeOrbit(gamma, [2,1]);

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]);

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 e-subsets 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"] );

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 i-1 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 vertex-colouring 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 newly-formed bipartite graph

Bicomponents(J42BPD);      ??

but if we try that on a non-bipartite graph it will return an empty list. On a non-connected graph it will of course be non-unique:

null4 := NullGraph(Group((1,2)), 4);;

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]);

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 non-simple 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);;

Specifying we only want those of size 3 would make this list even longer.

Robert Brignall May 2004

Home   |   Members   |   Library   |   Reports   |   Seminars   |   Conferences   |   Research   |   Publicity   |  Pictures   |   GAP   |   Webmail