Given a graph G, and a non-negative integer n, return the set of all vertices of G that have degree equal to n.
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.
Given a bipartite graph G, return its two partite sets in the form of a pair of subsets of V(G).
Given a vertex u of the graph G, return the degree of u, ie the number of edges incident to u.
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.
Given two vertices u and v belonging to a graph G, return the length of a shortest path from u to v. If u and v lie in different components, the value -1 is returned.
Given an edge e belonging to the graph G, return a set containing the two end vertices of e.
The set of all edges incident with the vertex u.
The maximum of the degrees of the vertices of G. This function returns two values: The maximum degree, and a vertex of G having that degree.
The minimum of the degrees of the vertices of G. This function returns two values: The minimum degree, and a vertex of G having that degree.
Given a vertex u of the graph G, return the set of vertices of G that are adjacent to u.
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.
Given a regular graph G, return the valence of G (the degree of any vertex).
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).
Given vertices u and v belonging to a digraph G, return the value true if there is an edge directed from vertex u to vertex v, otherwise false.
Returns true if the edge e is adjacent to the edge f, where e and f are edges belonging to the digraph G, otherwise false.
Given vertices u and v belonging to a digraph G, return the value true if there is not an edge directed from vertex u to vertex v, otherwise false.
Returns true if the edge e is not adjacent to the edge f, where e and f are edges belonging to the digraph G, otherwise false.
Returns true if the vertex u is an endpoint of the edge e, where u and e belong to the digraph G, otherwise false.
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.
Given a vertex u belonging to a connected digraph G, and a non--negative integer n, return the set of vertices of G that are at distance n or less from u. Thus, Ball(u, n) is the set of vertices of G that are connected to u by a directed path of length at most n.
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.
Given an edge e belonging to the digraph G, return a sequence of length two whose first component is the first vertex of e, and whose second component is the second vertex of e.
The number of edges directed into the vertex u belonging to the directed graph G.
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.
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.
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.
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.
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.
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.
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.
The number of edges of the form uv where u is a vertex belonging to the directed graph G.
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.
In the following functions, the graph is assumed to be a directed tree. This means it is a tree containing a root vertex and all edges are directed away from that vertex.
Returns true exactly when g is a tree having a vertex v such that all edges are directed away from v. In this case, the root vertex v is returned as a second value.
The root vertex of a rooted tree.
Returns true if and only if the graph containing v is directed as a rooted tree with v as root.
When the graph containing v is directed as a rooted tree, this returns the unique neighbouring vertex to v which is closer to the root vertex. If v is the root vertex, it is returned itself.
A sequence of vertexs comprising a path in a directed graph from u to v. The path does not necessarily respect the edge directions. Indeed it will first trace back to a common ancestor of u and v and then follow edge directions to v.
The sequence of vertices on the vertex path from u to v having valency at least 3.[Next][Prev] [Right] [Left] [Up] [Index] [Root]