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.
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 \).