Distances, Paths and Circuits in a Graph

The distance functions apply to graphs as well as to digraphs.

Contents

Distances, Paths and Circuits in a Possibly Weighted Graph

There are a few distance and path functions that take into account the fact that the edges of the graph under consideration may be weighted. If the graph is not weighted, then the distance between two vertices is taken to be the length of the shortest path between the vertices. For more details on distance and paths functions in weighted graphs, refer to Section Distances, Shortest Paths and Minimum Weight Trees in Chapter MULTIGRAPHS.

Reachable(u, v) : GrphVert, GrphVert -> BoolElt
Return true if and only if vertices u and v of a graph G are in the same component of G.
Distance(u, v) : GrphVert, GrphVert -> RngIntElt
Given two vertices u and v belonging to a graph G, return the length of a shortest path from u to v. If the graph is weighted, the function returns the total weight of the path from u to v. Results in an error if there is no path in G from u to v.
Geodesic(u, v) : GrphVert, GrphVert -> [GrphVert]
Given vertices u and v belonging to the graph G, return a sequence of vertices u = v1, v2, ..., vn = v such that the sequence of edges v1v2, v2v3, ... vn - 1vn forms a shortest path joining u and v. Results in an error if there is no path in G from u to v.

Distances, Paths and Circuits in a Non-Weighted Graph

The distance between two vertices is understood in its usual meaning of being the length of a shortest path between the vertices. The diameter of a graph is the maximum of the distances between every pair of vertices in the graph. Alternatively, it is the length of the longest geodesic in the graph. The distance and path functions listed below do not take account of the fact that the graph edges may be weighted.

Diameter(G) : Grph -> RngIntElt
The maximum of the distances between every two vertices in the graph G is returned. If G is not connected, the value -1 is returned.

DiameterPath(G) : Grph -> [GrphVert]
A sequence of vertices defining a longest geodesic in the graph G, if the G is connected, or the empty sequence if G is not connected.
Ball(u, n) : GrphVert, RngIntElt -> { GrphVert }
Given a vertex u belonging to a graph G, and a non-negative integer n, return the set of vertices of G that are at distance n or less from u.
Sphere(u, n) : GrphVert, RngIntElt -> { GrphVert }
Given a vertex u belonging to the graph G, and a non-negative integer n, return the set of vertices of G that are at distance n from u.
DistancePartition(u) : GrphVert -> [ { GrphVert } ]
Given a vertex u belonging to the graph G, return the partition P0 ∪P1 ∪ ... ∪Pd of the vertex-set of G, where Pi is the set of vertices lying at distance i from vertex u. The partition is returned as a sequence of sets. Any vertices not connected to u are treated as being at infinite distance from u and are returned as the last set of the partition.
IsEquitable(G, P) : GrphUnd, { { GrphVert } } -> BoolElt
IsEquitable(G, P) : GrphUnd, { { RngIntElt } } -> BoolElt
Given a partition P of the vertex-set V(G) of the graph G, return the value true if P is an equitable partition.
EquitablePartition(P, G) : { { GrphVert } }, GrphUnd -> { { GrphVert } }
EquitablePartition(P, G) : { { RngIntElt } }, GrphUnd -> { { GrphVert } }
Given a partition P of the vertex-set V(G) of the graph G, return the coarsest partition of V(G) that refines P and which is equitable.
Girth(G) : GrphUnd -> RngIntElt
The girth of graph G, i.e. the length of a shortest cycle. To see how the automorphism group of G is computed see Subsection Graph Colouring and Automorphism Group.
GirthCycle(G) : GrphUnd -> [GrphVert]
A cycle of shortest length in the graph G. To see how the automorphism group of G is computed see Subsection Graph Colouring and Automorphism Group.
V2.28, 13 July 2023