This chapter describes functions to determine certain special vertex subsets of a graph.

`ConnectedComponent( `

`, `

` )`

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 ]

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

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

`DistanceSet( `

`, `

`, `

` )`

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

`Layers( `

`, `

` )`

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

`IndependentSet( `

` )`

`IndependentSet( `

`, `

` )`

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

grape manual

June 2018