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" );
Loading GRAPE 2.31 (GRaph Algorithms using PErmutation groups),
by L.H.Soicher@qmw.ac.uk.
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 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 ) )
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 ] ] )
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 )
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 ∩ 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> 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" ] )
64.10 Functions to inspect graphs, vertices and edges
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
64.31 Functions to determine regularity properties of graphs
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 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 ] ]
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 ] ]
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.
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 ] ]
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.
See also CollapsedAdjacencyMat.
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.
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 ]
64.45 Functions to construct new graphs from old
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(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
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 ] ] )
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∈ 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 ] ] ] )
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 ] ]
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 )
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.
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 ]
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.
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 ] ]
gap3-jm