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

Previous Up Top Next
Index