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\).
- 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 [Chr75] 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\).