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

# 3 Functions to inspect graphs, vertices and edges

### Sections

This chapter describes functions to inspect graphs, vertices and edges.

## 3.1 IsGraph

• `IsGraph( `obj` )`

This boolean function returns `true` if and only if obj, which can be an object of arbitrary type, is a graph.

```gap> IsGraph( 1 );
false
gap> IsGraph( JohnsonGraph( 3, 2 ) );
true
```

## 3.2 OrderGraph

• `OrderGraph( `gamma` )`

This function returns the number of vertices (the order) of the graph gamma.

```gap> OrderGraph( JohnsonGraph( 4, 2 ) );
6
```

## 3.3 IsVertex

• `IsVertex( `gamma`, `v` )`

This boolean function returns `true` if and only if v is vertex of the graph gamma.

```gap> gamma := JohnsonGraph( 3, 2 );;
gap> IsVertex( gamma, 1 );
true
gap> IsVertex( gamma, 4 );
false
```

## 3.4 VertexName

• `VertexName( `gamma`, `v` )`

This function returns (an immutable copy of) the name of vertex v in the graph gamma.

```gap> VertexName( JohnsonGraph(4,2), 6 );
[ 3, 4 ]
```

## 3.5 VertexNames

• `VertexNames( `gamma` )`

This function returns (an immutable copy of) the list of vertex-names for the graph gamma. The i-th element of this list is the name of vertex i.

```gap> VertexNames( JohnsonGraph(4,2) );
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]
```

## 3.6 Vertices

• `Vertices( `gamma` )`

This function returns the vertex-set {1,..., gamma`.order`} of the graph gamma.

```gap> Vertices( JohnsonGraph( 4, 2 ) );
[ 1 .. 6 ]
```

## 3.7 VertexDegree

• `VertexDegree( `gamma`, `v` )`

This function returns the (out)degree of the vertex v of the graph gamma.

```gap> VertexDegree( JohnsonGraph( 3, 2 ), 1 );
2
```

## 3.8 VertexDegrees

• `VertexDegrees( `gamma` )`

This function returns the set of vertex (out)degrees for the graph gamma.

```gap> VertexDegrees( JohnsonGraph( 4, 2 ) );
[ 4 ]
```

## 3.9 IsLoopy

• `IsLoopy( `gamma` )`

This boolean function returns `true` if and only if the graph gamma has a loop, i.e. an edge of the form [x,x].

```gap> IsLoopy( JohnsonGraph( 4, 2 ) );
false
gap> IsLoopy( CompleteGraph( Group( (1,2,3), (1,2) ), 3 ) );
false
gap> IsLoopy( CompleteGraph( Group( (1,2,3), (1,2) ), 3, true ) );
true
```

## 3.10 IsSimpleGraph

• `IsSimpleGraph( `gamma` )`

This boolean function returns `true` if and only if the graph gamma is simple, i.e. has no loops and whenever [x,y] is an edge then so is [y,x].

```gap> IsSimpleGraph( CompleteGraph( Group( (1,2,3) ), 3 ) );
true
gap> IsSimpleGraph( CompleteGraph( Group( (1,2,3) ), 3, true ) );
false
```

• `Adjacency( `gamma`, `v` )`

This function returns (a copy of) the set of vertices of the graph gamma adjacent to the vertex v of gamma. A vertex w is adjacent to v if and only if [v,w] is an edge.

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

## 3.12 IsEdge

• `IsEdge( `gamma`, `e` )`

This boolean function returns `true` if and only if e is an edge of the graph gamma.

```gap> IsEdge( JohnsonGraph( 4, 2 ), [ 1, 2 ] );
true
gap> IsEdge( JohnsonGraph( 4, 2 ), [ 1, 6 ] );
false
```

## 3.13 DirectedEdges

• `DirectedEdges( `gamma` )`

This function returns the set of directed (ordered) edges of the graph gamma.

```gap> gamma := JohnsonGraph( 4, 3 );
rec( isGraph := true, order := 4, group := Group([ (1,4,3,2), (3,4) ]),
schreierVector := [ -1, 1, 1, 1 ], adjacencies := [ [ 2, 3, 4 ] ],
representatives := [ 1 ],
names := [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ],
isSimple := true )
gap> DirectedEdges( gamma );
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 1 ], [ 2, 3 ], [ 2, 4 ], [ 3, 1 ],
[ 3, 2 ], [ 3, 4 ], [ 4, 1 ], [ 4, 2 ], [ 4, 3 ] ]
gap> UndirectedEdges( gamma );
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]
```

## 3.14 UndirectedEdges

• `UndirectedEdges( `gamma` )`

This function returns the set of undirected (unordered) edges of gamma, which must be a simple graph.

```gap> gamma := JohnsonGraph( 4, 3 );
rec( isGraph := true, order := 4, group := Group([ (1,4,3,2), (3,4) ]),
schreierVector := [ -1, 1, 1, 1 ], adjacencies := [ [ 2, 3, 4 ] ],
representatives := [ 1 ],
names := [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ],
isSimple := true )
gap> DirectedEdges( gamma );
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 1 ], [ 2, 3 ], [ 2, 4 ], [ 3, 1 ],
[ 3, 2 ], [ 3, 4 ], [ 4, 1 ], [ 4, 2 ], [ 4, 3 ] ]
gap> UndirectedEdges( gamma );
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]
```

## 3.15 Distance

• `Distance( `gamma`, `X`, `Y` )`
• `Distance( `gamma`, `X`, `Y`, `G` )`

This function returns the distance from X to Y in gamma. The parameters X and Y may be vertices or nonempty lists of vertices. We define the distance d(X,Y) from X to Y to be the minimum length of a (directed) path joining a vertex of X to a vertex of Y if such a path exists, and -1 otherwise.

The optional parameter G, if present, is assumed to be a subgroup of Aut(gamma) fixing X setwise. Including such a G can speed up the function.

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

## 3.16 Diameter

• `Diameter( `gamma` )`

This function returns the diameter of gamma. A diameter of -1 is returned if gamma is not (strongly) connected. Otherwise, the diameter of gamma is equal to the maximum (directed) distance d(x,y) in gamma (as x and y range over all the vertices of gamma).

```gap> Diameter( JohnsonGraph( 5, 3 ) );
2
gap> Diameter( JohnsonGraph( 5, 4 ) );
1
```

## 3.17 Girth

• `Girth( `gamma` )`

This function returns the girth of gamma, which must be a simple graph. A girth of -1 is returned if gamma is a forest. Otherwise the girth is the length of a shortest cycle in gamma.

```gap> Girth( JohnsonGraph( 4, 2 ) );
3
```

## 3.18 IsConnectedGraph

• `IsConnectedGraph( `gamma` )`

This boolean function returns `true` if and only if the graph gamma is (strongly) connected, i.e. there is a (directed) path from x to y for every pair of vertices x,y of gamma.

```gap> IsConnectedGraph( JohnsonGraph(4,2) );
true
gap> IsConnectedGraph( NullGraph(SymmetricGroup(4)) );
false
```

## 3.19 IsBipartite

• `IsBipartite( `gamma` )`

This boolean function returns `true` if and only if the graph gamma, which must be simple, is bipartite, i.e. if the vertex-set can be expressed as the disjoint union of two sets, on each of which gamma induces a null graph (these two sets are called the bicomponents or parts of gamma).

```gap> gamma := JohnsonGraph(4,2);
rec(
isGraph := true,
order := 6,
group := Group( [ (1,4,6,3)(2,5), (2,4)(3,5) ] ),
schreierVector := [ -1, 2, 1, 1, 1, 1 ],
adjacencies := [ [ 2, 3, 4, 5 ] ],
representatives := [ 1 ],
names := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ],
isSimple := true )
gap> IsBipartite(gamma);
false
gap> delta := BipartiteDouble(gamma);
rec(
isGraph := true,
order := 12,
group := Group( [ ( 1, 4, 6, 3)( 2, 5)( 7,10,12, 9)( 8,11),
( 2, 4)( 3, 5)( 8,10)( 9,11), ( 1, 7)( 2, 8)( 3, 9)( 4,10)( 5,11)
( 6,12) ] ),
schreierVector := [ -1, 2, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3 ],
adjacencies := [ [ 8, 9, 10, 11 ] ],
representatives := [ 1 ],
isSimple := true,
names := [ [ [ 1, 2 ], "+" ], [ [ 1, 3 ], "+" ], [ [ 1, 4 ], "+" ],
[ [ 2, 3 ], "+" ], [ [ 2, 4 ], "+" ], [ [ 3, 4 ], "+" ],
[ [ 1, 2 ], "-" ], [ [ 1, 3 ], "-" ], [ [ 1, 4 ], "-" ],
[ [ 2, 3 ], "-" ], [ [ 2, 4 ], "-" ], [ [ 3, 4 ], "-" ] ] )
gap> IsBipartite(delta);
true
```

## 3.20 IsNullGraph

• `IsNullGraph( `gamma` )`

This boolean function returns `true` if and only if the graph gamma has no edges.

```gap> IsNullGraph( CompleteGraph( Group(()), 3 ) );
false
gap> IsNullGraph( CompleteGraph( Group(()), 1 ) );
true
```

## 3.21 IsCompleteGraph

• `IsCompleteGraph( `gamma` )`
• `IsCompleteGraph( `gamma`, `mustloops` )`

This boolean function returns `true` if and only if the graph gamma is a complete graph. The optional boolean parameter mustloops determines whether all loops must be present for gamma to be considered a complete graph (default: `false` (loops are ignored)).

```gap> IsCompleteGraph( NullGraph( Group(()), 3 ) );