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

# 5 Some special vertex subsets of a graph

### Sections

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

## 5.1 ConnectedComponent

• `ConnectedComponent( `gamma`, `v` )`

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.

```gap> ConnectedComponent( NullGraph( Group((1,2)) ), 2 );
[ 2 ]
gap> ConnectedComponent( JohnsonGraph(4,2), 2 );
[ 1, 2, 3, 4, 5, 6 ]
```

## 5.2 ConnectedComponents

• `ConnectedComponents( `gamma` )`

This function returns a list of the vertex sets of the connected components of gamma, which must be a simple graph.

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

• `Bicomponents( `gamma` )`

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.

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

• `DistanceSet( `gamma`, `distances`, `V` )`
• `DistanceSet( `gamma`, `distances`, `V`, `G` )`

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.

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

## 5.5 Layers

• `Layers( `gamma`, `V` )`
• `Layers( `gamma`, `V`, `G` )`

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.

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

## 5.6 IndependentSet

• `IndependentSet( `gamma` )`
• `IndependentSet( `gamma`, `indset` )`
• `IndependentSet( `gamma`, `indset`, `forbidden` )`

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
March 2021