# 64 Grape

This chapter describes the main functions of the GRAPE (Version 2.31) share library package for computing with graphs and groups. All functions described here are written entirely in the GAP3 language, except for the automorphism group and isomorphism testing functions, which make use of B. McKay's \nauty (Version 1.7) package Nau90.

GRAPE is primarily designed for the construction and analysis of graphs related to permutation groups and finite geometries. Special emphasis is placed on the determination of regularity properties and subgraph structure. The GRAPE philosophy is that a graph Γ always comes together with a known subgroup G of Aut(Γ), and that G is used to reduce the storage and CPU-time requirements for calculations with Γ (see Soi91). Of course G may be the trivial group, and in this case GRAPE algorithms will perform more slowly than strictly combinatorial algorithms (although this degradation in performance is hopefully never more than a fixed constant factor).

In general GRAPE deals with directed graphs which may have loops but have no multiple edges. However, many GRAPE functions only work for simple graphs (i.e. no loops, and whenever [x,y] is an edge then so is [y,x]), but these functions will check if an input graph is simple.

In GRAPE, a graph gamma is stored as a record, with mandatory components `isGraph`, `order`, `group`, `schreierVector`, `representatives`, and `adjacencies`. Usually, the user need not be aware of this record structure, and is strongly advised only to use GRAPE functions to construct and modify graphs.

The `order` component contains the number of vertices of gamma. The vertices of gamma are always 1,..,gamma.order, but they may also be given names, either by a user or by a function constructing a graph (e.g. `InducedSubgraph`, `BipartiteDouble`, `QuotientGraph`). The `names` component, if present, records these names. If the `names` component is not present (the user may, for example, choose to unbind it), then the names are taken to be 1,...,gamma.order. The `group` component records the the GAP3 permutation group associated with gamma (this group must be a subgroup of Aut(gamma)). The `representatives` component records a set of orbit representatives for gamma.group on the vertices of gamma, with gamma.adjacencies[i] being the set of vertices adjacent to gamma.representatives[i]. The only mandatory component which may change once a graph is initially constructed is `adjacencies` (when an edge orbit of gamma.group is added to, or removed from, gamma). A graph record may also have some of the optional components `isSimple`, `autGroup`, and `canonicalLabelling`, which record information about that graph.

GRAPE has the ability to make use of certain random group theoretical algorithms, which can result in time and store savings. The use of these random methods may be switched on and off by the global boolean variable `GRAPE_RANDOM`, whose default value is `false` (random methods not used). Even if random methods are used, no function described below depends on the correctness of such a randomly computed result. For these functions the use of these random methods only influences the time and store taken. All global variables used by GRAPE start with `GRAPE_`.

The user who is interested in knowing more about the GRAPE system, and its advanced use, should consult Soi91 and the GRAPE source code.

Before using any of the functions described in this chapter you must load the package by calling the statement

```    gap> RequirePackage( "grape" );

by L.H.Soicher@qmw.ac.uk.
```

## 64.1 Functions to construct and modify graphs

The following sections describe the functions used to construct and modify graphs.

## 64.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 GAP3 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 n\x n adjacency matrix A for a graph X, so that the vertices of X are {1,...,n}, and [i,j] is an edge of X if and only if A[i][j]=1. Suppose also that G ≤ 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 ] ] ) ```

## 64.3 EdgeOrbitsGraph

`EdgeOrbitsGraph( G, E )`
`EdgeOrbitsGraph( G, E, n )`

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∈ E eG , and associated (permutation) group G, which must act naturally on {1,...,n}. The parameter E 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 the number of vertices is the largest point moved by a generator of G.

Note that G may be the trivial permutation group (`Group( () )` in GAP3 notation), in which case the (directed) edges of gamma are simply those in the list E.

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

## 64.4 NullGraph

`NullGraph( G )`
`NullGraph( G, n )`

This function returns the null graph on n vertices, with associated (permutation) group G. The parameter n may be omitted, in which case the number of vertices is the largest point moved by a generator of G.

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

## 64.5 CompleteGraph

`CompleteGraph( G )`
`CompleteGraph( G, n )`
`CompleteGraph( G, n, mustloops )`

This function returns a complete graph on n vertices with associated (permutation) group G. The parameter n may be omitted, in which case the number of vertices is the largest point moved by a generator of G. The optional boolean parameter mustloops determines whether the complete graph has all loops present or no loops (default: `false` (no loops)).

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

## 64.6 JohnsonGraph

`JohnsonGraph( n, e )`

This function returns a graph gamma isomorphic to the Johnson graph, whose vertices 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 image of the the symmetric group Sn acting on the e-subsets of {1,...,n}.

```    gap> JohnsonGraph(5,3);
rec(
isGraph := true,
order := 10,
group := Group( ( 1, 8)( 2, 9)( 4,10), ( 1, 5)( 2, 6)( 7,10),
( 1, 3)( 4, 6)( 7, 9), ( 2, 3)( 4, 5)( 7, 8) ),
schreierVector := [ -1, 4, 3, 4, 2, 3, 4, 1, 3, 2 ],
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 ) ```

`AddEdgeOrbit( gamma, e )`
`AddEdgeOrbit( gamma, e, H )`

This procedure adds the edge orbit <e>gamma.group to the edge set of 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 greatly speed up the procedure.

Note that if gamma.group is trivial then this procedure simply adds the single edge e to gamma.

```    gap> gamma := NullGraph( Group( (1,3), (1,2)(3,4) ) );
rec(
isGraph := true,
order := 4,
group := Group( (1,3), (1,2)(3,4) ),
schreierVector := [ -1, 2, 1, 2 ],
adjacencies := [ [  ] ],
representatives := [ 1 ],
isSimple := true )
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 ) ```

## 64.8 RemoveEdgeOrbit

`RemoveEdgeOrbit( gamma, e )`
`RemoveEdgeOrbit( gamma, e, H )`

This procedure removes the edge orbit <e>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 greatly speed up the procedure.

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

## 64.9 AssignVertexNames

`AssignVertexNames( gamma, names )`

This function allows the user to give new names to the vertices of gamma, by specifying a list names of vertex names for the vertices of gamma, such that <names>[i] contains the user's name for the i-th vertex of gamma.

```    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" ] ) ```

## 64.10 Functions to inspect graphs, vertices and edges

The next sections describe functions to inspect graphs, vertices and edges.

## 64.11 IsGraph

`IsGraph( obj )`

This boolean function returns `true` if and only if obj, which can be an object of arbitrary type, is a graph.

```    gap> IsGraph( 1 );
false
gap> IsGraph( JohnsonGraph( 3, 2 ) );
true ```

## 64.12 OrderGraph

`OrderGraph( gamma )`

This function returns the number of vertices (order) of the graph gamma.

```    gap> OrderGraph( JohnsonGraph( 4, 2 ) );
6 ```

## 64.13 IsVertex

`IsVertex( gamma, v )`

This boolean function returns `true` if and only if v is vertex of gamma.

```    gap> gamma := JohnsonGraph( 3, 2 );;
gap> IsVertex( gamma, 1 );
true
gap> IsVertex( gamma, 4 );
false ```

## 64.14 VertexName

`VertexName( gamma, v )`

This function returns (a copy of) the name of the vertex v of gamma.

```    gap> VertexName( JohnsonGraph(4,2), 6 );
[ 3, 4 ] ```

## 64.15 Vertices

`Vertices( gamma )`

This function returns the vertex set {1,...,gamma.order} of the graph gamma.

```    gap> Vertices( JohnsonGraph( 4, 2 ) );
[ 1 .. 6 ] ```

## 64.16 VertexDegree

`VertexDegree( gamma, v )`

This function returns the (out)degree of the vertex v of the graph gamma.

```    gap> VertexDegree( JohnsonGraph( 3, 2 ), 1 );
2 ```

## 64.17 VertexDegrees

`VertexDegrees( gamma )`

This function returns the set of vertex (out)degrees for the graph gamma.

```    gap> VertexDegrees( JohnsonGraph( 4, 2 ) );
[ 4 ] ```

## 64.18 IsLoopy

`IsLoopy( gamma )`

This boolean function returns `true` if and only if the graph gamma has a loop, that is, an edge of the form [x,x].

```    gap> IsLoopy( JohnsonGraph( 4, 2 ) );
false
gap> IsLoopy( CompleteGraph( Group( (1,2,3), (1,2) ), 3 ) );
false
gap> IsLoopy( CompleteGraph( Group( (1,2,3), (1,2) ), 3, true ) );
true ```

## 64.19 IsSimpleGraph

`IsSimpleGraph( gamma )`

This boolean function returns `true` if and only if the graph gamma is simple, that is, has no loops and whenever [x,y] is an edge then so is [y,x].

```    gap> IsSimpleGraph( CompleteGraph( Group( (1,2,3) ), 3 ) );
true
gap> IsSimpleGraph( CompleteGraph( Group( (1,2,3) ), 3, true ) );
false ```

`Adjacency( gamma, v )`

This function returns (a copy of) the set of vertices of gamma adjacent to vertex v. A vertex w is adjacent to v if and only if [v,w] is an edge.

```    gap> Adjacency( JohnsonGraph( 4, 2 ), 1 );
[ 2, 3, 4, 5 ]
gap> Adjacency( JohnsonGraph( 4, 2 ), 6 );
[ 2, 3, 4, 5 ] ```

## 64.21 IsEdge

`IsEdge( gamma, e )`

This boolean function returns `true` if and only if e is an edge of gamma.

```    gap> IsEdge( JohnsonGraph( 4, 2 ), [ 1, 2 ] );
true
gap> IsEdge( JohnsonGraph( 4, 2 ), [ 1, 6 ] );
false ```

## 64.22 DirectedEdges

`DirectedEdges( gamma )`

This function returns the set of directed (ordered) edges of the graph gamma.

```    gap> gamma := JohnsonGraph( 3, 2 );
rec(
isGraph := true,
order := 3,
group := Group( (1,3), (1,2) ),
schreierVector := [ -1, 2, 1 ],
adjacencies := [ [ 2, 3 ] ],
representatives := [ 1 ],
names := [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ],
isSimple := true )
gap> DirectedEdges( gamma );
[ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ] ]
gap> UndirectedEdges( gamma );
[ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ] ```

## 64.23 UndirectedEdges

`UndirectedEdges( gamma )`

This function returns the set of undirected (unordered) edges of gamma, which must be a simple graph.

```    gap> gamma := JohnsonGraph( 3, 2 );
rec(
isGraph := true,
order := 3,
group := Group( (1,3), (1,2) ),
schreierVector := [ -1, 2, 1 ],
adjacencies := [ [ 2, 3 ] ],
representatives := [ 1 ],
names := [ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ],
isSimple := true )
gap> DirectedEdges( gamma );
[ [ 1, 2 ], [ 1, 3 ], [ 2, 1 ], [ 2, 3 ], [ 3, 1 ], [ 3, 2 ] ]
gap> UndirectedEdges( gamma );
[ [ 1, 2 ], [ 1, 3 ], [ 2, 3 ] ] ```

## 64.24 Distance

`Distance( gamma, X, Y )`
`Distance( gamma, X, Y, G )`

This function returns the distance from X to Y in gamma. The parameters X and Y may be vertices or vertex sets. We define the distance d(X,Y) from X to Y to be the minimum length of a (directed) path joining a vertex of X to a vertex of Y if such a path exists, and -1 otherwise.

The optional parameter G, if present, is assumed to be a subgroup of Aut(gamma) fixing X setwise. Including such a G can speed up the function.

```    gap> Distance( JohnsonGraph(4,2), 1, 6 );
2
gap> Distance( JohnsonGraph(4,2), 1, 5 );
1 ```

## 64.25 Diameter

`Diameter( gamma )`

This function returns the diameter of gamma. A diameter of -1 is returned if gamma is not (strongly) connected.

```    gap> Diameter( JohnsonGraph( 5, 3 ) );
2
gap> Diameter( JohnsonGraph( 5, 4 ) );
1 ```

## 64.26 Girth

`Girth( gamma )`

This function returns the girth of gamma, which must be a simple graph. A girth of -1 is returned if gamma is a forest.

```    gap> Girth( JohnsonGraph( 4, 2 ) );
3 ```

## 64.27 IsConnectedGraph

`IsConnectedGraph( gamma )`

This boolean function returns `true` if and only if gamma is (strongly) connected, i.e. if there is a (directed) path from x to y for every pair of vertices x,y of gamma.

```    gap> IsConnectedGraph( JohnsonGraph(4,2) );
true
gap> IsConnectedGraph( NullGraph(SymmetricGroup(4)) );
false ```

## 64.28 IsBipartite

`IsBipartite( gamma )`

This boolean function returns `true` if and only if the graph gamma, which must be simple, is bipartite, i.e. if the vertex set can be partitioned into two null graphs (which are called bicomponents or parts of gamma).

```    gap> gamma := JohnsonGraph(4,2);
rec(
isGraph := true,
order := 6,
group := Group( (1,5)(2,6), (1,3)(4,6), (2,3)(4,5) ),
schreierVector := [ -1, 3, 2, 3, 1, 2 ],
adjacencies := [ [ 2, 3, 4, 5 ] ],
representatives := [ 1 ],
names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ],
[ 3, 4 ] ],
isSimple := true )
gap> IsBipartite(gamma);
false
gap> delta := BipartiteDouble(gamma);
rec(
isGraph := true,
order := 12,
group := Group( ( 1, 5)( 2, 6)( 7,11)( 8,12), ( 1, 3)( 4, 6)( 7, 9)
(10,12), ( 2, 3)( 4, 5)( 8, 9)(10,11), ( 1, 7)( 2, 8)( 3, 9)
( 4,10)( 5,11)( 6,12) ),
schreierVector := [ -1, 3, 2, 3, 1, 2, 4, 4, 4, 4, 4, 4 ],
adjacencies := [ [ 8, 9, 10, 11 ] ],
representatives := [ 1 ],
isSimple := true,
names := [ [ [ 1, 2 ], "+" ], [ [ 1, 3 ], "+" ], [ [ 1, 4 ], "+" ],
[ [ 2, 3 ], "+" ], [ [ 2, 4 ], "+" ], [ [ 3, 4 ], "+" ],
[ [ 1, 2 ], "-" ], [ [ 1, 3 ], "-" ], [ [ 1, 4 ], "-" ],
[ [ 2, 3 ], "-" ], [ [ 2, 4 ], "-" ], [ [ 3, 4 ], "-" ] ] )
gap> IsBipartite(delta);
true ```

## 64.29 IsNullGraph

`IsNullGraph( gamma )`

This boolean function returns `true` if and only if the graph gamma has no edges.

```    gap> IsNullGraph( CompleteGraph( Group(()), 3 ) );
false
gap> IsNullGraph( CompleteGraph( Group(()), 1 ) );
true ```

## 64.30 IsCompleteGraph

`IsCompleteGraph( gamma )`
`IsCompleteGraph( gamma, mustloops )`

This boolean function returns `true` if and only if the graph gamma is a complete graph. The optional boolean parameter mustloops determines whether all loops must be present for gamma to be considered a complete graph (default: `false` (loops are ignored)).

```    gap> IsCompleteGraph( NullGraph( Group(()), 3 ) );
false
gap> IsCompleteGraph( NullGraph( Group(()), 1 ) );
true
gap> IsCompleteGraph( CompleteGraph(SymmetricGroup(3)), true );
false ```

## 64.31 Functions to determine regularity properties of graphs

The following sections describe functions to determine regularity properties of graphs.

## 64.32 IsRegularGraph

`IsRegularGraph( gamma )`

This boolean function returns `true` if and only if the graph gamma is (out)regular.

```    gap> IsRegularGraph( JohnsonGraph(4,2) );
true
gap> IsRegularGraph( EdgeOrbitsGraph(Group(()),[[1,2]],2) );
false ```

## 64.33 LocalParameters

`LocalParameters( gamma, V )`
`LocalParameters( gamma, V, G )`

This function determines any local parameters ci(V), ai(V), or bi(V) that simple, connected gamma may have, with respect to the singleton vertex or vertex set V (see BCN89). The function returns a list of triples, whose i-th element is [ci-1(V),ai-1(V),bi-1(V)], except that if some local parameter does not exist then a -1 is put in its place. This function can be used to determine whether a given subset of the vertices of a graph is a distance-regular code in that graph.

The optional parameter G, if present, is assumed to be a subgroup of Aut(gamma) fixing V (setwise). Including such a G can speed up the function.

```    gap> LocalParameters( JohnsonGraph(4,2), 1 );
[ [ 0, 0, 4 ], [ 1, 2, 1 ], [ 4, 0, 0 ] ]
gap> LocalParameters( JohnsonGraph(4,2), [1,6] );
[ [ 0, 0, 4 ], [ 2, 2, 0 ] ] ```

## 64.34 GlobalParameters

`GlobalParameters( gamma )`

In a similar way to `LocalParameters` (see LocalParameters), this function determines the global parameters ci,ai,bi of simple, connected gamma (see BCN89). The nonexistence of a global parameter is denoted by -1.

```    gap> gamma := JohnsonGraph(4,2);;
gap> GlobalParameters( gamma );
[ [ 0, 0, 4 ], [ 1, 2, 1 ], [ 4, 0, 0 ] ]
gap> GlobalParameters( BipartiteDouble(gamma) );
[ [ 0, 0, 4 ], [ 1, 0, 3 ], [ -1, 0, -1 ], [ 4, 0, 0 ] ] ```

## 64.35 IsDistanceRegular

`IsDistanceRegular( gamma )`

This boolean function returns `true` if and only if gamma is distance-regular, i.e. gamma is simple, connected, and all possible global parameters exist.

```    gap> gamma := JohnsonGraph(4,2);;
gap> IsDistanceRegular( gamma );
true
gap> IsDistanceRegular( BipartiteDouble(gamma) );
false ```

`CollapsedAdjacencyMat( G, gamma )`

This function returns the collapsed adjacency matrix for gamma, where the collapsing group is G. It is assumed that G is a subgroup of Aut(gamma).

The (i,j)-entry of the collapsed adjacency matrix equals the number of edges in { [x,y] | y ∈ j-th G-orbit }, where x is a fixed vertex in the i-th G-orbit.

```    gap> gamma := JohnsonGraph(4,2);;
gap> G := Stabilizer( gamma.group, 1 );;
[ [ 0, 4, 0 ], [ 1, 2, 1 ], [ 0, 4, 0 ] ] ```

## 64.37 OrbitalGraphIntersectionMatrices

`OrbitalGraphIntersectionMatrices( G )`
`OrbitalGraphIntersectionMatrices( G, H )`

This function returns a sequence of intersection matrices corresponding to the orbital graphs for the transitive permutation group G. An intersection matrix for an orbital graph gamma for G is a collapsed adjacency matrix of gamma, collapsed with respect to the stabilizer in G of a point.

If the optional parameter H is given then it is assumed to be the stabilizer in G of the point 1, and this information can speed up the function.

```    gap> OrbitalGraphIntersectionMatrices( SymmetricGroup(7) );
[ [ [ 1, 0 ], [ 0, 1 ] ], [ [ 0, 6 ], [ 1, 5 ] ] ] ```

## 64.38 Some special vertex subsets of a graph

The following sections describe functions for special vertex subsets of a graph.

## 64.39 ConnectedComponent

`ConnectedComponent( gamma, v )`

This function returns the set of all vertices in gamma which can be reached by a path starting at the vertex v. The graph gamma must be simple.

```    gap> ConnectedComponent( NullGraph( Group((1,2)) ), 2 );
[ 2 ]
gap> ConnectedComponent( JohnsonGraph(4,2), 2 );
[ 1, 2, 3, 4, 5, 6 ] ```

## 64.40 ConnectedComponents

`ConnectedComponents( gamma )`

This function returns a list of the vertex sets of the connected components of gamma, which must be a simple graph.

```    gap> ConnectedComponents( NullGraph( Group((1,2,3,4)) ) );
[ [ 1 ], [ 2 ], [ 3 ], [ 4 ] ]
gap> ConnectedComponents( JohnsonGraph(4,2) );
[ [ 1, 2, 3, 4, 5, 6 ] ] ```

## 64.41 Bicomponents

`Bicomponents( gamma )`

If the graph gamma, which must be simple, is bipartite, this function returns a length 2 list of bicomponents or parts of gamma, otherwise the empty list is returned.

Note: if gamma is not connected then its bicomponents are not necessarily uniquely determined. See also IsBipartite.

```    gap> Bicomponents( NullGraph(SymmetricGroup(4)) );
[ [ 1, 2, 3 ], [ 4 ] ]
gap> Bicomponents( JohnsonGraph(4,2) );
[  ] ```

## 64.42 DistanceSet

`DistanceSet( gamma, distances, V )`
`DistanceSet( gamma, distances, V, G )`

This function returns the set of vertices w of gamma, such that d(V,w) is in distances (a list or singleton distance).

The optional parameter G, if present, is assumed to be a subgroup of Aut(gamma) fixing V setwise. Including such a G can speed up the function.

```    gap> DistanceSet( JohnsonGraph(4,2), 1, [1,6] );
[ 2, 3, 4, 5 ] ```

## 64.43 Layers

`Layers( gamma, V )`
`Layers( gamma, V, G )`

This function returns a list whose i-th element is the set of vertices of gamma at distance i-1 from V, which may be a vertex set or a singleton vertex.

The optional parameter G, if present, is assumed to be a subgroup of Aut(gamma) which fixes V setwise. Including such a G can speed up the function.

```    gap> Layers( JohnsonGraph(4,2), 6 );
[ [ 6 ], [ 2, 3, 4, 5 ], [ 1 ] ] ```

## 64.44 IndependentSet

`IndependentSet( gamma )`
`IndependentSet( gamma, indset )`
`IndependentSet( gamma, indset, forbidden )`

Returns a (hopefully large) independent set (coclique) of the graph gamma, which must be simple. At present, a greedy algorithm is used. The returned independent set will contain the (assumed) independent set indset (default: `[]`), and not contain any element of forbidden (default: `[]`, in which case the returned independent set is maximal). An error is signalled if indset and forbidden have non-trivial intersection.

```    gap> IndependentSet( JohnsonGraph(4,2), [3] );
[ 3, 4 ] ```

## 64.45 Functions to construct new graphs from old

The following sections describe functions to construct new graphs from old ones.

## 64.46 InducedSubgraph

`InducedSubgraph( gamma, V )`
`InducedSubgraph( gamma, V, G )`

This function returns the subgraph of gamma induced on the vertex list V (which must not contain repeated elements). If the optional third parameter G is given, then it is assumed that G fixes V setwise, and is a group of automorphisms of the induced subgraph when restriced to V. This knowledge is then used to give an associated group to the induced subgraph. If no such G is given then the associated group is trivial.

```    gap> gamma := JohnsonGraph(4,2);;
gap> S := [2,3,4,5];;
gap> InducedSubgraph( gamma, S, Stabilizer(gamma.group,S,OnSets) );
rec(
isGraph := true,
order := 4,
group := Group( (2,3), (1,2)(3,4) ),
schreierVector := [ -1, 2, 1, 2 ],
adjacencies := [ [ 2, 3 ] ],
representatives := [ 1 ],
isSimple := true,
names := [ [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ] ] ) ```

## 64.47 DistanceSetInduced

`DistanceSetInduced( gamma, distances, V )`
`DistanceSetInduced( gamma, distances, V, G )`

This function returns the subgraph of gamma induced on the set of vertices w of gamma such that d(V,w) is in distances (a list or singleton distance).

The optional parameter G, if present, is assumed to be a subgroup of Aut(gamma) fixing V setwise. Including such a G can speed up the function.

```    gap> DistanceSetInduced( JohnsonGraph(4,2), [0,1], [1] );
rec(
isGraph := true,
order := 5,
group := Group( (2,3)(4,5), (2,5)(3,4) ),
schreierVector := [ -1, -2, 1, 2, 2 ],
adjacencies := [ [ 2, 3, 4, 5 ], [ 1, 3, 4 ] ],
representatives := [ 1, 2 ],
isSimple := true,
names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ] ] ) ```

## 64.48 DistanceGraph

`DistanceGraph( gamma, distances )`

This function returns the graph delta, with the same vertex set as gamma, such that [x,y] is an edge of delta if and only if d(x,y) (in gamma) is in the list distances.

```    gap> DistanceGraph( JohnsonGraph(4,2), [2] );
rec(
isGraph := true,
order := 6,
group := Group( (1,5)(2,6), (1,3)(4,6), (2,3)(4,5) ),
schreierVector := [ -1, 3, 2, 3, 1, 2 ],
adjacencies := [ [ 6 ] ],
representatives := [ 1 ],
names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ],
[ 3, 4 ] ],
isSimple := true )
gap> ConnectedComponents(last);
[ [ 1, 6 ], [ 2, 5 ], [ 3, 4 ] ] ```

## 64.49 ComplementGraph

`ComplementGraph( gamma )`
`ComplementGraph( gamma, comploops )`

This function returns the complement of the graph gamma. The optional boolean parameter comploops determines whether or not loops/nonloops are complemented (default: `false` (loops/nonloops are not complemented)).

```    gap> ComplementGraph( NullGraph(SymmetricGroup(3)) );
rec(
isGraph := true,
order := 3,
group := Group( (1,3), (2,3) ),
schreierVector := [ -1, 2, 1 ],
adjacencies := [ [ 2, 3 ] ],
representatives := [ 1 ],
isSimple := true )
gap> IsLoopy(last);
false
gap> IsLoopy(ComplementGraph(NullGraph(SymmetricGroup(3)),true));
true ```

## 64.50 PointGraph

`PointGraph( gamma )`
`PointGraph( gamma, v )`

Assuming that gamma is simple, connected, and bipartite, this function returns the induced subgraph on the connected component of `DistanceGraph(gamma,2)` containing the vertex v (default: <v>=1).

Thus, if gamma is the incidence graph of a connected geometry, and v represents a point, then the point graph of the geometry is returned.

```    gap> BipartiteDouble( CompleteGraph(SymmetricGroup(4)) );;
gap> PointGraph(last);
rec(
isGraph := true,
order := 4,
group := Group( (3,4), (2,4), (1,4) ),
schreierVector := [ -1, 2, 1, 3 ],
adjacencies := [ [ 2, 3, 4 ] ],
representatives := [ 1 ],
isSimple := true,
names := [ [ 1, "+" ], [ 2, "+" ], [ 3, "+" ], [ 4, "+" ] ] )
gap> IsCompleteGraph(last);
true ```

## 64.51 EdgeGraph

`EdgeGraph( gamma )`

This function returns the edge graph, also called the line graph, of the simple graph gamma.

This edge graph delta has the unordered edges of gamma as vertices, and e is joined to f in delta precisely when |e∩ f|=1.

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

## 64.52 UnderlyingGraph

`UnderlyingGraph( gamma )`

This function returns the underlying graph delta of gamma. The graph delta has the same vertex set as gamma, and has an edge [x,y] precisely when gamma has an edge [x,y] or an edge [y,x]. This function also sets the `isSimple` components of gamma and delta.

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

## 64.53 QuotientGraph

`QuotientGraph( gamma, R )`

Let S be the smallest gamma.group-invariant equivalence relation on the vertices of gamma, such that S contains the relation R (which should be a list of ordered pairs (length 2 lists) of vertices of gamma). Then this function returns a graph isomorphic to the quotient delta of the graph gamma, defined as follows. The vertices of delta are the equivalence classes of S, and [X,Y] is an edge of delta if and only if [x,y] is an edge of gamma for some x∈ X, y∈ Y.

```    gap> gamma := JohnsonGraph(4,2);;
gap> QuotientGraph( gamma, [[1,6]] );
rec(
isGraph := true,
order := 3,
group := Group( (1,2), (1,3), (2,3) ),
schreierVector := [ -1, 1, 2 ],
adjacencies := [ [ 2, 3 ] ],
representatives := [ 1 ],
isSimple := true,
names := [ [ [ 1, 2 ], [ 3, 4 ] ], [ [ 1, 3 ], [ 2, 4 ] ],
[ [ 1, 4 ], [ 2, 3 ] ] ] ) ```

## 64.54 BipartiteDouble

`BipartiteDouble( gamma )`

This function returns the bipartite double of the graph gamma, as defined in BCN89.

```    gap> gamma := JohnsonGraph(4,2);
rec(
isGraph := true,
order := 6,
group := Group( (1,5)(2,6), (1,3)(4,6), (2,3)(4,5) ),
schreierVector := [ -1, 3, 2, 3, 1, 2 ],
adjacencies := [ [ 2, 3, 4, 5 ] ],
representatives := [ 1 ],
names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ],
[ 3, 4 ] ],
isSimple := true )
gap> IsBipartite(gamma);
false
gap> delta := BipartiteDouble(gamma);
rec(
isGraph := true,
order := 12,
group := Group( ( 1, 5)( 2, 6)( 7,11)( 8,12), ( 1, 3)( 4, 6)( 7, 9)
(10,12), ( 2, 3)( 4, 5)( 8, 9)(10,11), ( 1, 7)( 2, 8)( 3, 9)
( 4,10)( 5,11)( 6,12) ),
schreierVector := [ -1, 3, 2, 3, 1, 2, 4, 4, 4, 4, 4, 4 ],
adjacencies := [ [ 8, 9, 10, 11 ] ],
representatives := [ 1 ],
isSimple := true,
names := [ [ [ 1, 2 ], "+" ], [ [ 1, 3 ], "+" ], [ [ 1, 4 ], "+" ],
[ [ 2, 3 ], "+" ], [ [ 2, 4 ], "+" ], [ [ 3, 4 ], "+" ],
[ [ 1, 2 ], "-" ], [ [ 1, 3 ], "-" ], [ [ 1, 4 ], "-" ],
[ [ 2, 3 ], "-" ], [ [ 2, 4 ], "-" ], [ [ 3, 4 ], "-" ] ] )
gap> IsBipartite(delta);
true ```

## 64.55 GeodesicsGraph

`GeodesicsGraph( gamma, x, y )`

This function returns the the graph induced on the set of geodesics between vertices x and y, but not including x or y. This function is only for a simple graph gamma.

```    gap> GeodesicsGraph( JohnsonGraph(4,2), 1, 6 );
rec(
isGraph := true,
order := 4,
group := Group( (1,3)(2,4), (1,4)(2,3), (1,3,4,2) ),
schreierVector := [ -1, 2, 1, 2 ],
adjacencies := [ [ 2, 3 ] ],
representatives := [ 1 ],
isSimple := true,
names := [ [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ] ] )
gap> GlobalParameters(last);
[ [ 0, 0, 2 ], [ 1, 0, 1 ], [ 2, 0, 0 ] ] ```

## 64.56 CollapsedIndependentOrbitsGraph

`CollapsedIndependentOrbitsGraph( G, gamma )`
`CollapsedIndependentOrbitsGraph( G, gamma, N )`

Given a subgroup G of the automorphism group of the graph gamma, this function returns a graph isomorphic to delta, defined as follows. The vertices of delta are those G-orbits of the vertices of gamma that are independent sets, and x is not joined to y in delta if and only if x∪ y is an independent set in gamma.

If the optional parameter N is given, then it is assumed to be a subgroup of Aut(gamma) preserving the set of G-orbits of the vertices of gamma (for example, the normalizer in gamma.group of G). This information can make the function more efficient.

```    gap> G := Group( (1,2) );;
gap> gamma := NullGraph( SymmetricGroup(3) );;
gap> CollapsedIndependentOrbitsGraph( G, gamma );
rec(
isGraph := true,
order := 2,
group := Group( () ),
schreierVector := [ -1, -2 ],
adjacencies := [ [  ], [  ] ],
representatives := [ 1, 2 ],
isSimple := true,
names := [ [ 1, 2 ], [ 3 ] ] ) ```

## 64.57 CollapsedCompleteOrbitsGraph

`CollapsedCompleteOrbitsGraph( G, gamma )`
`CollapsedCompleteOrbitsGraph( G, gamma, N )`

Given a subgroup G of the automorphism group of the simple graph gamma, this function returns a graph isomorphic to delta, defined as follows. The vertices of delta are those G-orbits of the vertices of gamma on which complete subgraphs are induced in gamma, and x is joined to y in delta if and only if x≠y and the subgraph of gamma induced on x∪ y is a complete graph.

If the optional parameter N is given, then it is assumed to be a subgroup of Aut(gamma) preserving the set of G-orbits of the vertices of gamma (for example, the normalizer in gamma.group of G). This information can make the function more efficient.

```    gap> G := Group( (1,2) );;
gap> gamma := NullGraph( SymmetricGroup(3) );;
gap> CollapsedCompleteOrbitsGraph( G, gamma );
rec(
isGraph := true,
order := 1,
group := Group( () ),
schreierVector := [ -1 ],
adjacencies := [ [  ] ],
representatives := [ 1 ],
names := [ [ 3 ] ],
isSimple := true )
gap> gamma := CompleteGraph( SymmetricGroup(3) );;
gap> CollapsedCompleteOrbitsGraph( G, gamma );
rec(
isGraph := true,
order := 2,
group := Group( () ),
schreierVector := [ -1, -2 ],
adjacencies := [ [ 2 ], [ 1 ] ],
representatives := [ 1, 2 ],
names := [ [ 1, 2 ], [ 3 ] ],
isSimple := true ) ```

## 64.58 NewGroupGraph

`NewGroupGraph( G, gamma )`

This function returns a copy delta of gamma, except that the group associated with delta is G, which is a assumed to be a subgroup of Aut(delta).

Note that the result of some functions of a graph depend on the group associated with that graph (which must always be a subgroup of the automorphism group of the graph).

```    gap> gamma := JohnsonGraph(4,2);;
gap> aut := AutGroupGraph(gamma);
Group( (3,4), (2,3)(4,5), (1,2)(5,6) )
gap> Size(gamma.group);
24
gap> Size(aut);
48
gap> delta := NewGroupGraph( aut, gamma );;
gap> Size(delta.group);
48
gap> IsIsomorphicGraph( gamma, delta );
true ```

## 64.59 Vertex-Colouring and Complete Subgraphs

The following sections describe functions for vertex-colouring or constructing complete subgraphs of given graphs.

## 64.60 VertexColouring

`VertexColouring( gamma )`

This function returns a proper vertex-colouring C for the graph gamma, which must be simple.

This proper vertex-colouring C is a list of natural numbers, indexed by the vertices of gamma, and has the property that C[i]≠C[j] whenever [i,j] is an edge of gamma. At present a greedy algorithm is used.

```    gap> VertexColouring( JohnsonGraph(4,2) );
[ 1, 2, 3, 3, 2, 1 ] ```

## 64.61 CompleteSubgraphs

`CompleteSubgraphs( gamma )`
`CompleteSubgraphs( gamma, k )`
`CompleteSubgraphs( gamma, k, alls )`

This function returns a set K of complete subgraphs of gamma, which must be a simple graph. A complete subgraph is represented by its vertex set. If <k> > -1 then the elements of K each have size k, otherwise the elements of K represent maximal complete subgraphs of gamma. The default for k is -1, i.e. maximal complete subgraphs.

The optional boolean parameter alls controls how many complete subgraphs are returned. If alls is `true` (the default), then K will contain (perhaps properly) a set of gamma.group orbit-representatives of the size k (if <k> > -1) or maximal (if <k> < 0) complete subgraphs of gamma.

If alls is `false` then K will contain at most one element. In this case, if <k> < 0 then K will contain just one maximal complete subgraph, and if <k> > -1 then K will contain a complete subgraph of size k if and only if such a subgraph is contained in gamma.

```    gap> gamma := JohnsonGraph(5,2);;
gap> CompleteSubgraphs(gamma);
[ [ 1, 2, 3, 4 ], [ 1, 2, 5 ] ]
gap> CompleteSubgraphs(gamma,2,false);
[ [ 1, 2 ] ] ```

## 64.62 CompleteSubgraphsOfGivenSize

`CompleteSubgraphsOfGivenSize( gamma, k )`
`CompleteSubgraphsOfGivenSize( gamma, k, alls )`
`CompleteSubgraphsOfGivenSize( gamma, k, alls, maxi )`
`CompleteSubgraphsOfGivenSize( gamma, k, alls, maxi, colnum )`

Let gamma be a simple graph and <k> > 0. This function returns a set K of complete subgraphs of size k of gamma, if such subgraphs exist (else the empty set is returned). A complete subgraph is represented by its vertex set. This function is more efficient for its purpose than the more general function `CompleteSubgraphs`.

The boolean parameter alls is used to control how many complete subgraphs are returned. If alls is true (the default), then K will contain (perhaps properly) a set of gamma.group orbit-representatives of the size k complete subgraphs of gamma. If alls is false then K will contain at most one element, and will contain one element if and only if gamma contains a complete subgraph of size k.

If the boolean parameter maxi is bound and has value true, then it is assumed that all complete subgraphs of size k of gamma are maximal.

If the optional rational parameter colnum is given, then a sensible value is

`OrderGraph(gamma)/Length(Set(VertexColouring(gamma)))`.

The use of this parameter may speed up the function.

```    gap> gamma := JohnsonGraph(5,2);;
gap> CompleteSubgraphsOfGivenSize(gamma,5);
[  ]
gap> CompleteSubgraphsOfGivenSize(gamma,4,true,true);
[ [ 1, 2, 3, 4 ] ]
gap> gamma := NewGroupGraph( Group(()), gamma );;
gap> CompleteSubgraphsOfGivenSize(gamma,4,true,true);
[ [ 1, 2, 3, 4 ], [ 1, 5, 6, 7 ], [ 2, 5, 8, 9 ], [ 3, 6, 8, 10 ],
[ 4, 7, 9, 10 ] ] ```

## 64.63 Functions depending on nauty

For convenience, GRAPE provides a (somewhat primitive) interface to Brendan McKay's \nauty (Version 1.7) package (see Nau90) for calculating automorphism groups of vertex-coloured graphs, and for testing graph isomorphism.

## 64.64 AutGroupGraph

`AutGroupGraph( gamma )`
`AutGroupGraph( gamma, colouring )`

The first version of this function returns the automorphism group of the (directed) graph gamma, using \nauty.

In the second version, colouring is a vertex-colouring of gamma, and the subgroup of Aut(gamma) preserving this colouring is returned. Here, a colouring should be given as a list of sets, forming a partion of the vertices. The set for the last colour may be omitted. Note that we do not require that adjacent vertices have different colours.

```    gap> gamma := JohnsonGraph(4,2);;
gap> Size(AutGroupGraph(gamma));
48
gap> Size(AutGroupGraph(gamma,[[1,6]]));
16 ```

## 64.65 IsIsomorphicGraph

`IsIsomorphicGraph( gamma1, gamma2 )`

This boolean function uses the \nauty program to test the isomorphism of gamma1 with gamma2. The value `true` is returned if and only if the graphs are isomorphic (as directed, uncoloured graphs).

This function creates or uses the record component `canonicalLabelling` of a graph. As noted in Nau90, a canonical labelling given by \nauty can depend on the version of \nauty (Version 1.7 in GRAPE 2.31), certain parameters of \nauty (always set the same by GRAPE 2.31), and the compiler and computer used. If you use the `canonicalLabelling` component (say by using `IsIsomorphicGraph`) of a graph stored on a file, then you must be sure that this field was created in the same environment in which you are presently computing. If in doubt, unbind the `canonicalLabelling` component of the graph before testing isomorphism.

```    gap> gamma := JohnsonGraph(7,4);;
gap> delta := JohnsonGraph(7,3);;
gap> IsIsomorphicGraph( gamma, delta );
true ```

## 64.66 An example

We conclude this chapter with a simple example to illustrate further the use of GRAPE.

In this example we construct the Petersen graph P, and its edge graph (often called line graph) EP. We compute the (global) parameters of EP, and so verify that EP is distance-regular (see BCN89). We also show that there is just one orbit of 1-factors of P under the automorphism group of P (but you should read the documentation of the function `CompleteSubgraphsOfGivenSize` to see exactly what that function does).

```    gap> P := 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 ] ] )
gap> Diameter(P);
2
gap> Girth(P);
5
gap> EP := EdgeGraph(P);
rec(
isGraph := true,
order := 15,
group := Group( ( 1, 4)( 2, 5)( 3, 6)(10,11)(12,13)(14,15), ( 1, 7)
( 2, 8)( 3, 9)(10,15)(11,13)(12,14), ( 2, 3)( 4, 7)( 5,10)( 6,11)
( 8,12)( 9,14), ( 1, 3)( 4,12)( 5, 8)( 6,13)( 7,10)( 9,15) ),
schreierVector := [ -1, 3, 4, 1, 3, 1, 2, 3, 2, 4, 1, 4, 1, 2, 2 ],
adjacencies := [ [ 2, 3, 13, 15 ] ],
representatives := [ 1 ],
isSimple := true,
names := [ [ [ 1, 2 ], [ 3, 5 ] ], [ [ 1, 2 ], [ 4, 5 ] ],
[ [ 1, 2 ], [ 3, 4 ] ], [ [ 1, 3 ], [ 2, 5 ] ],
[ [ 1, 4 ], [ 2, 5 ] ], [ [ 2, 5 ], [ 3, 4 ] ],
[ [ 1, 5 ], [ 2, 3 ] ], [ [ 1, 5 ], [ 2, 4 ] ],
[ [ 1, 5 ], [ 3, 4 ] ], [ [ 1, 4 ], [ 2, 3 ] ],
[ [ 2, 3 ], [ 4, 5 ] ], [ [ 1, 3 ], [ 2, 4 ] ],
[ [ 2, 4 ], [ 3, 5 ] ], [ [ 1, 3 ], [ 4, 5 ] ],
[ [ 1, 4 ], [ 3, 5 ] ] ] )
gap> GlobalParameters(EP);
[ [ 0, 0, 4 ], [ 1, 1, 2 ], [ 1, 2, 1 ], [ 4, 0, 0 ] ]
gap> CompleteSubgraphsOfGivenSize(ComplementGraph(EP),5);
[ [ 1, 5, 9, 11, 12 ] ] ```

gap3-jm
19 Feb 2018