# Adjacency and Degree

## Adjacency and Degree Functions for a Graph

### `Degree(u): GrphVert -> RngIntElt`

Given a vertex $u$ of the graph $G$, return the degree of $u$, ie the number of edges incident to $u$.

### `Alldeg(G, n): GrphUnd, RngIntElt -> { GrphVert}`

Given a graph $G$, and a non-negative integer $n$, return the set of all vertices of $G$ that have degree equal to $n$.

### `MaximumDegree(G): GrphUnd -> RngIntElt, GrphVert`

### `Maxdeg(G): GrphUnd -> RngIntElt, GrphVert`

The maximum of the degrees of the vertices of the graph $G$. This function returns two values: the maximum degree, and a vertex of $G$ having that degree.

### `MinimumDegree(G): GrphUnd -> RngIntElt, GrphVert`

### `Mindeg(G): GrphUnd -> RngIntElt, GrphVert`

The minimum of the degrees of the vertices of the graph $G$. This function returns two values: the minimum degree, and a vertex of $G$ having that degree.

### `DegreeSequence(G): Grph -> [ { GrphVert} ]`

Given a graph $G$ such that the maximum degree of any vertex of $G$ is $r$, return a sequence $D$ of length $r+1$, such that $D[i]$, $1 \leq i \leq r+1$, is the number of vertices in $G$ having degree $i-1$.

### `Valence(G): GrphUnd -> RngIntElt`

Given a regular graph $G$, return the valence of $G$ (the degree of any vertex).

### `Neighbours(u): GrphVert -> { GrphVert}`

### `Neighbors(u): GrphVert -> { GrphVert}`

Given a vertex $u$ of the graph $G$, return the set of vertices of $G$ that are adjacent to $u$.

### `IncidentEdges(u): GrphVert -> { GrphEdge}`

The set of all edges incident with the vertex $u$.

### `Bipartition(G): GrphUnd -> [ { GrphVert} ]`

Given a bipartite graph $G$, return its two partite sets in the form of a pair of subsets of $V(G)$.

### `MinimumDominatingSet(G): GrphUnd -> SetEnum`

A dominating set $S$ of a graph $G$ is such that the vertices of $S$ together with the vertices adjacent to vertices in $S$ form the vertex-set of $G$. A dominating set $S$ is minimal if no proper subset of $S$ is a dominating set. A minimum dominating set is a minimal dominating set of smallest size. The algorithm implemented is a backtrack algorithm (see [[Christofides, 1975](../../references.md#cite-christo75)] p. 41).

## Adjacency and Degree Functions for a Digraph

### `InDegree(u): GrphVert -> RngIntElt`

The number of edges directed into the vertex $u$ belonging to the directed graph $G$.

### `OutDegree(u): GrphVert -> RngIntElt`

The number of edges of the form $uv$ where $u$ is a vertex belonging to the directed graph $G$.

### `Degree(u): GrphVert -> RngIntElt`

Given a vertex $u$ belonging to the digraph $G$, return the total degree of $u$, i.e. the sum of the in–degree and out–degree for $u$.

### `Alldeg(G, n): GrphDir, RngIntElt -> { GrphVert}`

Given a digraph $G$, and a non–negative integer $n$, return the set of all vertices of $G$ that have total degree equal to $n$.

### `MaximumInDegree(G): GrphDir -> RngIntElt, GrphVert`

### `Maxindeg(G): GrphDir -> RngIntElt, GrphVert`

The maximum indegree of the vertices of the digraph $G$. This function returns two values: the maximum indegree, and the first vertex of $G$ having that degree.

### `MaximumOutDegree(G): GrphDir -> RngIntElt, GrphVert`

### `Maxoutdeg(G): GrphDir -> RngIntElt, GrphVert`

The maximum outdegree of the vertices of the digraph $G$. This function returns two values: the maximum outdegree, and the first vertex of $G$ having that degree.

### `MinimumInDegree(G): GrphDir -> RngIntElt, GrphVert`

### `Minindeg(G): GrphDir -> RngIntElt, GrphVert`

The minimum indegree of the vertices of the digraph $G$. This function returns two values: the minimum indegree, and the first vertex of $G$ having that degree.

### `MinimumOutDegree(G): GrphDir -> RngIntElt, GrphVert`

### `Minoutdeg(G): GrphDir -> RngIntElt, GrphVert`

The minimum outdegree of the vertices of the digraph $G$. This function returns two values: the minimum outdegree, and the first vertex of $G$ having that degree.

### `MaximumDegree(G): GrphDir -> RngIntElt, GrphVert`

### `Maxdeg(G): GrphDir -> RngIntElt, GrphVert`

The maximum total degree of the vertices of the digraph $G$. This function returns two values: the maximum total degree, and the first vertex of $G$ having that degree.

### `MinimumDegree(G): GrphDir -> RngIntElt, GrphVert`

### `Mindeg(G): GrphDir -> RngIntElt, GrphVert`

The minimum total degree of the vertices of the digraph $G$. This function returns two values: the minimum total degree, and the first vertex of $G$ having that degree.

### `DegreeSequence(G): Grph -> [ { GrphVert} ]`

Given a digraph $G$ such that the maximum degree of any vertex of $G$ is $r$, return a sequence $D$ of length $r+1$, such that $D[i]$, $1 \leq i \leq r+1$, is the number of vertices in $G$ having degree $i-1$.

### `InNeighbours(u): GrphVert -> { GrphVert}`

### `InNeighbors(u): GrphVert -> { GrphVert}`

Given a vertex $u$ of the digraph $G$, return the set containing all vertices $v$ such that $vu$ is an edge in the digraph, i.e. the starting points of all edges that are directed into the vertex $u$.

### `OutNeighbours(u): GrphVert -> { GrphVert}`

### `OutNeighbors(u): GrphVert -> { GrphVert}`

Given a vertex $u$ of the digraph $G$, return the set of vertices $v$ of $G$ such that $uv$ is an edge in the graph $G$, i.e. the set of vertices $v$ that are the end vertices of edges directed from $u$ to $v$.

### `IncidentEdges(u): GrphVert -> { GrphEdge}`

The set of all edges incident with the vertex $u$.