Adjacency and Degree

Contents

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 ≤i ≤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 [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 ≤i ≤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.
V2.28, 13 July 2023