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

Subsections

  1. Functions to construct and modify graphs
  2. Graph
  3. EdgeOrbitsGraph
  4. NullGraph
  5. CompleteGraph
  6. JohnsonGraph
  7. AddEdgeOrbit
  8. RemoveEdgeOrbit
  9. AssignVertexNames
  10. Functions to inspect graphs, vertices and edges
  11. IsGraph
  12. OrderGraph
  13. IsVertex
  14. VertexName
  15. Vertices
  16. VertexDegree
  17. VertexDegrees
  18. IsLoopy
  19. IsSimpleGraph
  20. Adjacency
  21. IsEdge
  22. DirectedEdges
  23. UndirectedEdges
  24. Distance
  25. Diameter
  26. Girth
  27. IsConnectedGraph
  28. IsBipartite
  29. IsNullGraph
  30. IsCompleteGraph
  31. Functions to determine regularity properties of graphs
  32. IsRegularGraph
  33. LocalParameters
  34. GlobalParameters
  35. IsDistanceRegular
  36. CollapsedAdjacencyMat
  37. OrbitalGraphIntersectionMatrices
  38. Some special vertex subsets of a graph
  39. ConnectedComponent
  40. ConnectedComponents
  41. Bicomponents
  42. DistanceSet
  43. Layers
  44. IndependentSet
  45. Functions to construct new graphs from old
  46. InducedSubgraph
  47. DistanceSetInduced
  48. DistanceGraph
  49. ComplementGraph
  50. PointGraph
  51. EdgeGraph
  52. UnderlyingGraph
  53. QuotientGraph
  54. BipartiteDouble
  55. GeodesicsGraph
  56. CollapsedIndependentOrbitsGraph
  57. CollapsedCompleteOrbitsGraph
  58. NewGroupGraph
  59. Vertex-Colouring and Complete Subgraphs
  60. VertexColouring
  61. CompleteSubgraphs
  62. CompleteSubgraphsOfGivenSize
  63. Functions depending on nauty
  64. AutGroupGraph
  65. IsIsomorphicGraph
  66. An example

63.1 Functions to construct and modify graphs

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

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

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

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

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 ) 

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

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 ) 

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

63.7 AddEdgeOrbit

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 ) 

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

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

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

63.10 Functions to inspect graphs, vertices and edges

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

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

63.12 OrderGraph

OrderGraph( gamma )

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

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

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

63.14 VertexName

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 ] 

63.15 Vertices

Vertices( gamma )

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

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

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

63.17 VertexDegrees

VertexDegrees( gamma )

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

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

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

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

63.20 Adjacency

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 ] 

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

63.22 DirectedEdges

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

63.23 UndirectedEdges

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

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

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

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

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

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

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 

63.29 IsNullGraph

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 

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

See also CompleteGraph.

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

63.31 Functions to determine regularity properties of graphs

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

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

63.33 LocalParameters

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

63.34 GlobalParameters

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

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

63.36 CollapsedAdjacencyMat

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

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

63.38 Some special vertex subsets of a graph

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

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

See also ConnectedComponents.

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

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

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

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

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

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

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

63.45 Functions to construct new graphs from old

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

63.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 ] ] ) 

63.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 ] ] ) 

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

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

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

63.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 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 ] ] ) 

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

63.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 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 ] ] ] ) 

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

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

63.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 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 ] ] ) 

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

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

63.59 Vertex-Colouring and Complete Subgraphs

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

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

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

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

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

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

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

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

Previous Up Next
Index

GAP 3.4.4
April 1997