The following sections describe functions for (proper) vertex-colouring
or determining complete subgraphs of given graphs. The function
CompleteSubgraphsOfGivenSize
can also be used to determine the
complete subgraphs with given vertex-weight sum in a vertex-weighted
graphindexvertex-weighted graph, where the weights can be positive
integers or non-zero vectors of non-negative integers.
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 positive integers (the colours), indexed by the vertices of gamma, with the property that C [i] ≠ C [j] whenever [i,j] is an edge of gamma. At present a greedy algorithm is used, and the number of colours used is by no means guaranteed to be minimal.
gap> VertexColouring( JohnsonGraph(4,2) ); [ 1, 3, 2, 2, 3, 1 ]
CompleteSubgraphs(
gamma )
CompleteSubgraphs(
gamma,
k )
CompleteSubgraphs(
gamma,
k,
alls )
Let gamma be a simple graph and k an integer. This function returns
a set K of complete subgraphs of gamma, where a complete subgraph is
represented by its vertex-set. If k is non-negative then the elements
of K each have size k, otherwise the elements of K represent maximal
complete subgraphs of gamma. (A maximal complete subgraph of gamma
is a complete subgraph of gamma which is not properly contained in
another complete subgraph of gamma.) The default for k is −1,
i.e. maximal complete subgraphs. See also CompleteSubgraphsOfGivenSize
,
which can be used to compute the maximal complete subgraphs of given
size, and can also be used to determine the (maximal or otherwise)
complete subgraphs with given vertex-weight sum in a vertex-weighted
graph.
The optional parameter alls controls how many complete subgraphs are returned. The valid values for alls are 0, 1 (the default), and 2.
Warning: Using the default value of 1 for alls (see below) means that
more than one element may be returned for some gamma
.group
orbit(s)
of the required complete subgraphs. To obtain just one element from each
gamma
.group
orbit of the required complete subgraphs, you must give
the value 2 to the parameter alls.
If alls=0 (or false
for backward compatibility) then K will contain
at most one element. In this case, if k is negative then K will
contain just one maximal complete subgraph, and if k is non-negative
then K will contain a complete subgraph of size k if and only if
such a subgraph is contained in gamma.
If alls=1 (or true
for backward compatibility) then K will contain
(perhaps properly) a set of gamma
.group
orbit-representatives of
the maximal (if k is negative) or size k (if k is non-negative)
complete subgraphs of gamma.
If alls=2 then K will be a set of gamma
.group
orbit-representatives of the maximal (if k is negative) or size k
(if k is non-negative) complete subgraphs of gamma. This option
can be more costly than when alls=1.
Before applying CompleteSubgraphs
, one may want to associate the full
automorphism group of gamma with gamma, via gamma
:=
NewGroupGraph( AutGroupGraph(
gamma),
gamma );
.
An alternative name for this function is Cliques
indexCliques.
See also CompleteSubgraphsOfGivenSize.
gap> gamma := JohnsonGraph(5,2); rec( isGraph := true, order := 10, group := Group([ ( 1, 5, 8,10, 4)( 2, 6, 9, 3, 7), ( 2, 5)( 3, 6)( 4, 7) ]), schreierVector := [ -1, 2, 2, 1, 1, 1, 2, 1, 1, 1 ], adjacencies := [ [ 2, 3, 4, 5, 6, 7 ] ], representatives := [ 1 ], names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 3, 4 ], [ 3, 5 ], [ 4, 5 ] ], isSimple := true ) gap> CompleteSubgraphs(gamma); [ [ 1, 2, 3, 4 ], [ 1, 2, 5 ] ] gap> CompleteSubgraphs(gamma,3,2); [ [ 1, 2, 3 ], [ 1, 2, 5 ] ] gap> CompleteSubgraphs(gamma,-1,0); [ [ 1, 2, 5 ] ]
CompleteSubgraphsOfGivenSize(
gamma,
k )
CompleteSubgraphsOfGivenSize(
gamma,
k,
alls )
CompleteSubgraphsOfGivenSize(
gamma,
k,
alls,
maxi )
CompleteSubgraphsOfGivenSize(
gamma,
k,
alls,
maxi,
col )
CompleteSubgraphsOfGivenSize(
gamma,
k,
alls,
maxi,
col,
wts )
Let gamma be a simple graph, and k a non-negative integer or vector of non-negative integers. This function returns a set K (possibly empty) of complete subgraphs of size k of gamma. The vertices may have weights, which should be non-zero integers if k is an integer and non-zero d-vectors of non-negative integers if k is a d-vector, and in these cases, a complete subgraph of size k means a complete subgraph whose vertex-weights sum to k. The exact nature of the set K depends on the values of the parameters supplied to this function. A complete subgraph is represented by its vertex-set.
The optional parameter alls controls how many complete subgraphs are returned. The valid values for alls are 0, 1 (the default), and 2.
Warning: Using the default value of 1 for alls (see below) means that
more than one element may be returned for some gamma
.group
orbit(s)
of the required complete subgraphs. To obtain just one element from each
gamma
.group
orbit of the required complete subgraphs, you must give
the value 2 to the parameter alls.
If alls=0 (or false
for backward compatibility) then K will
contain at most one element. If maxi=false
then K will contain one
element if and only if gamma contains a complete subgraph of size k.
If maxi=true
then K will contain one element if and only if gamma
contains a maximal complete subgraph of size k, in which case K
will contain (the vertex-set of) such a maximal complete subgraph.
(A maximal complete subgraph of gamma is a complete subgraph of
gamma which is not properly contained in another complete subgraph
of gamma.)
If alls=1 (or true
for backward compatibility) and maxi=false
,
then K will contain (perhaps properly) a set of gamma
.group
orbit-representatives of the size k complete subgraphs of gamma.
If alls=1 (the default) and maxi=true
, then K will contain
(perhaps properly) a set of gamma
.group
orbit-representatives of
the size k maximal complete subgraphs of gamma.
If alls=2 and maxi=false
, then K will be a set of gamma
.group
orbit-representatives of the size k complete subgraphs of gamma.
If alls=2 and maxi=true
then K will be a set of gamma
.group
orbit-representatives of the size k maximal complete subgraphs
of gamma. This option can be more costly than when alls=1.
The optional parameter maxi controls whether only maximal complete
subgraphs of size k are returned. The default is false
, which means
that non-maximal as well as maximal complete subgraphs of size k are
returned. If maxi=true
then only maximal complete subgraphs of size
k are returned. (Previous to version 4.1 of GRAPE, maxi=true
meant that it was assumed (but not checked) that all complete subgraphs
of size k were maximal.)
The optional boolean parameter col is used to determine whether or not
partial proper vertex-colouring is used to cut down the search tree. The
default is true
, which says to use this partial colouring. For backward
compatibility, col a rational number means the same as col=true
.
The optional parameter wts should be a list of vertex-weights; the list
should be of length gamma
.order
, with the i-th element being the
weight of vertex i. The weights must be all positive integers if k
is an integer, and all non-zero d-vectors of non-negative integers
if k is a d-vector. The default is that all weights are equal to 1.
(Recall that a complete subgraph of size k means a complete subgraph
whose vertex-weights sum to k.)
If wts is a list of integers, then this list must be gamma
.group
invariant, where the action permutes the list positions in the natural
way.
If wts is a list of d-vectors then we assume that gamma
.group
acts
on the set of all integer d-vectors by permuting vector positions, such
that, for all v in [1..
gamma.order]
and all g in gamma
.group
,
we have wts [vg] = wts [v]g (where the first action is OnPoints
and for the second action, if ig=j then (wts [v]g)[j]=wts [v][i]),
and that we also have k g=k . These assumptions are not checked
by the function, and the use of vector-weights is primarily for advanced
users of GRAPE.
An alternative name for this function is
CliquesOfGivenSize
indexCliquesOfGivenSize.
See also CompleteSubgraphs.
gap> gamma:=JohnsonGraph(6,2); rec( isGraph := true, order := 15, group := Group([ ( 1, 6,10,13,15, 5)( 2, 7,11,14, 4, 9)( 3, 8,12), ( 2, 6)( 3, 7)( 4, 8)( 5, 9) ]), schreierVector := [ -1, 2, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1 ], adjacencies := [ [ 2, 3, 4, 5, 6, 7, 8, 9 ] ], representatives := [ 1 ], names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 1, 6 ], [ 2, 3 ], [ 2, 4 ], [ 2, 5 ], [ 2, 6 ], [ 3, 4 ], [ 3, 5 ], [ 3, 6 ], [ 4, 5 ], [ 4, 6 ], [ 5, 6 ] ], isSimple := true ) gap> CompleteSubgraphsOfGivenSize(gamma,4); [ [ 1, 2, 3, 4 ] ] gap> CompleteSubgraphsOfGivenSize(gamma,4,1,true); [ ] gap> CompleteSubgraphsOfGivenSize(gamma,5,2,true); [ [ 1, 2, 3, 4, 5 ] ] gap> delta:=NewGroupGraph(Group(()),gamma);; gap> CompleteSubgraphsOfGivenSize(delta,5,2,true); [ [ 1, 2, 3, 4, 5 ], [ 1, 6, 7, 8, 9 ], [ 2, 6, 10, 11, 12 ], [ 3, 7, 10, 13, 14 ], [ 4, 8, 11, 13, 15 ], [ 5, 9, 12, 14, 15 ] ] gap> CompleteSubgraphsOfGivenSize(delta,5,0); [ [ 1, 2, 3, 4, 5 ] ] gap> CompleteSubgraphsOfGivenSize(delta,5,1,false,true, > [1,2,3,4,5,6,7,8,7,6,5,4,3,2,1]); [ [ 1, 4 ], [ 2, 3 ], [ 3, 14 ], [ 4, 15 ], [ 5 ], [ 11 ], [ 12, 15 ], [ 13, 14 ] ]
[Up] [Previous] [Next] [Index]
grape manual