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

` )`

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

` )`

`CompleteSubgraphs( `

`, `

` )`

`CompleteSubgraphs( `

`, `

`, `

` )`

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

`, `

` )`

`CompleteSubgraphsOfGivenSize( `

`, `

`, `

` )`

`CompleteSubgraphsOfGivenSize( `

`, `

`, `

`, `

` )`

`CompleteSubgraphsOfGivenSize( `

`, `

`, `

`, `

`, `

` )`

`CompleteSubgraphsOfGivenSize( `

`, `

`, `

`, `

`, `

`, `

` )`

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* [*v*^{g}] = *wts* [*v*]^{g} (where the first action is `OnPoints`

and for the second action, if *i*^{g}=*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

January 2016