5 Some special vertex subsets of a graph

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 ] 

5.2 ConnectedComponents

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

5.3 Bicomponents

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 bipartite but not connected, then its set of bicomponents is not uniquely determined.

See also IsBipartite.

gap> Bicomponents( NullGraph(SymmetricGroup(4)) );
[ [ 1 .. 3 ], [ 4 ] ]
gap> Bicomponents( JohnsonGraph(4,2) );
[  ]
gap> Bicomponents( BipartiteDouble( JohnsonGraph(4,2) ) );
[ [ 1, 2, 3, 4, 5, 6 ], [ 7, 8, 9, 10, 11, 12 ] ]

5.4 DistanceSet

Let V be a vertex or a nonempty list of vertices of gamma. 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.

See also Distance and DistanceSetInduced.

gap> DistanceSet( JohnsonGraph(4,2), 1, [1,6] );
[ 2, 3, 4, 5 ] 

5.5 Layers

Let V be a vertex or a nonempty list of vertices of gamma. This function returns a list whose i-th element is the set of vertices of gamma at distance i-1 from V.

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.

See also Distance.

gap> Layers( JohnsonGraph(4,2), 6 );
[ [ 6 ], [ 2, 3, 4, 5 ], [ 1 ] ] 

5.6 IndependentSet

Returns a (hopefully large) independent set of the graph gamma, which must be simple. An independent set of gamma is a set of vertices of gamma, no two of which are joined by an edge. 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.

See also CompleteSubgraphs and CompleteSubgraphsOfGivenSize, which can be used on the complement graph of gamma to look seriously for independent sets.

gap> IndependentSet( JohnsonGraph(4,2), [3] );
[ 3, 4 ] 

[Up] [Previous] [Next] [Index]