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
graph indexvertex-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, indexed by the vertices of gamma, with 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, 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. 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.
The value 2 provides a new feature in GRAPE from version 4.1, and
specifies that this function should compute a set of gamma
.group
-orbit
representatives of the required complete subgraphs.
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.
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).
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
(and which seems to be a good idea). 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 the second action is the assumed one on integer d-vectors), and
that kg=k (where this action is the assumed one on d-vectors).
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