The closed graph ball of radius centered at vertex iswhere is shortest-path distance. In an unweighted graph, distances count edges, so a noninteger radius gives the same set as its integer part. Vertices in other connected components have infinite distance and lie outside every finite-radius ball.
For the path , and is the whole vertex set. The sphere at radius one contains only ; a ball also contains its center and all smaller distances.
A graph ball is first a vertex set. If one wants a graph on those vertices, the induced subgraph convention must be specified. Ball growth, such as how changes with , records large-scale connectivity beyond the immediate vertex degree.
The average shortest path length averages graph distances over distinct ordered pairs of vertices. A nodal value averages distances from one specified vertex to all others. Disconnected pairs require a separate convention.
Given positive edge lengths on a graph, define the distance between two vertices bywhere ranges over finite graph paths. An absent path gives distance . On a finite connected graph, this is a metric: reversing and concatenating routes gives symmetry and the triangle inequality, while the least edge length bounds every nonempty path away from zero. It is also a metric on a connected locally finite graph, since every path leaving a fixed vertex pays at least the positive minimum of its finitely many incident edge lengths.
Positive edge lengths alone do not guarantee a metric on an arbitrary infinite graph. Join two vertices through intermediate vertices , with both edges having length . Then for every , so distinct vertices have distance zero. On each finite-distance component the general construction is a pseudometric; its zero-distance classes give a metric quotient.
If a connected graph has adjacency matrix and diameter , thenare linearly independent. For the largest index with a nonzero coefficient, choose vertices at distance ; the corresponding entries of all lower powers vanish, while by the walk count from powers of an adjacency matrix.
Articles by others on the same topic
In graph theory, the **distance** between two vertices (or nodes) in a graph is defined as the length of the shortest path connecting them. The length of a path is typically measured by the number of edges it contains. Therefore, the distance \( d(u, v) \) between two vertices \( u \) and \( v \) is the minimum number of edges that need to be traversed to get from \( u \) to \( v \).