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 **GAP** 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 *Gamma*
always comes together with a known subgroup *G* of *Aut(Gamma)*, and
that *G* is used to reduce the storage and CPU-time requirements for
calculations with *Gamma* (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 **GAP** 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" );Loading GRAPE 2.31 (GRaph Algorithms using PErmutation groups), by L.H.Soicher@qmw.ac.uk.

- Functions to construct and modify graphs
- Graph
- EdgeOrbitsGraph
- NullGraph
- CompleteGraph
- JohnsonGraph
- AddEdgeOrbit
- RemoveEdgeOrbit
- AssignVertexNames
- Functions to inspect graphs, vertices and edges
- IsGraph
- OrderGraph
- IsVertex
- VertexName
- Vertices
- VertexDegree
- VertexDegrees
- IsLoopy
- IsSimpleGraph
- Adjacency
- IsEdge
- DirectedEdges
- UndirectedEdges
- Distance
- Diameter
- Girth
- IsConnectedGraph
- IsBipartite
- IsNullGraph
- IsCompleteGraph
- Functions to determine regularity properties of graphs
- IsRegularGraph
- LocalParameters
- GlobalParameters
- IsDistanceRegular
- CollapsedAdjacencyMat
- OrbitalGraphIntersectionMatrices
- Some special vertex subsets of a graph
- ConnectedComponent
- ConnectedComponents
- Bicomponents
- DistanceSet
- Layers
- IndependentSet
- Functions to construct new graphs from old
- InducedSubgraph
- DistanceSetInduced
- DistanceGraph
- ComplementGraph
- PointGraph
- EdgeGraph
- UnderlyingGraph
- QuotientGraph
- BipartiteDouble
- GeodesicsGraph
- CollapsedIndependentOrbitsGraph
- CollapsedCompleteOrbitsGraph
- NewGroupGraph
- Vertex-Colouring and Complete Subgraphs
- VertexColouring
- CompleteSubgraphs
- CompleteSubgraphsOfGivenSize
- Functions depending on nauty
- AutGroupGraph
- IsIsomorphicGraph
- An example

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

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

(the concatenation of the distinct orbits of the elements in `G`, `L`, `act` ) )`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 ] ] )

`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 * cup _{e in <E>}, e^<G>*, 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
**GAP** 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 )

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

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( 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)).

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

`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 cap y| = <e>-1*. The group associated with
*gamma* is image of the the symmetric group *S_<n>* acting on the
`e`-subsets of *{1,ldots,<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> 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 )

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

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

A copy of `names` is assigned to `gamma.names`. See also 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" ] )

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

`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

`OrderGraph( `

`gamma` )

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

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

`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

`VertexName( `

`gamma`, `v` )

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

See also AssignVertexNames.

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

`Vertices( `

`gamma` )

This function returns the vertex set *{1,...,<gamma.order>}* of the
graph `gamma`.

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

`VertexDegree( `

`gamma`, `v` )

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

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

`VertexDegrees( `

`gamma` )

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

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

`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

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

`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

`DirectedEdges( `

`gamma` )

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

See also UndirectedEdges.

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

`UndirectedEdges( `

`gamma` )

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

See also DirectedEdges.

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

`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

`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

`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

`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

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

See also Bicomponents, EdgeGraph, and BipartiteDouble.

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

`IsNullGraph( `

`gamma` )

This boolean function returns `true`

if and only if the graph `gamma` has
no edges.

See also NullGraph.

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

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

See also CompleteGraph.

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

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

`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

`LocalParameters( `

`gamma`, `V` )

`LocalParameters( `

`gamma`, `V`, `G` )

This function determines any **local parameters** *c_i(<V>)*, *a_i(<V>)*,
or *b_i(<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
*[c_{i-1}(<V>),a_{i-1}(<V>),b_{i-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 ] ]

`GlobalParameters( `

`gamma` )

In a similar way to `LocalParameters`

(see LocalParameters), this
function determines the **global parameters** *c_i,a_i,b_i* 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 ] ]

`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 in j*-th `G`-orbit *}*, where *x* is a fixed
vertex in the *i*-th `G`-orbit.

See also OrbitalGraphIntersectionMatrices.

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

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

See also CollapsedAdjacencyMat.

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

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

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

See also ConnectedComponents.

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

`ConnectedComponents( `

`gamma` )

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

See also ConnectedComponent.

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

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

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

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

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

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

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

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

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

`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

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

containing the vertex `gamma`,2)`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

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

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

`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 in X*,
*y in 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 ] ] ] )

`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

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

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

`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 *xnot=y* and the subgraph of
`gamma` induced on *x cup 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 )

`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

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

`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]not=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 ]

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

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

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.

`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

`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

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

GAP 3.4.4

April 1997