Graph distance ( $d (u, v)$ )

d (u, v)

between connected vertices is the least length of a path joining them.

Table of contents
- Path metric Graph distance
- Graph diameter Graph distance
  - Linear independence of adjacency powers up to the diameter Graph diameter

Path metric ( $ρ$ )

Given positive edge lengths

ℓ (e)

, the path metric is the infimum of

\sum_{e \in γ} ℓ (e)

over paths

γ

joining two vertices.

Graph diameter ( $d (G)$ )

The diameter of a connected finite graph is the maximum distance between two vertices.

Linear independence of adjacency powers up to the diameter

If a connected graph has adjacency matrix

A

d

, then

I, A, \dots, A^{d}

are linearly independent. For the largest index

k

with a nonzero coefficient, choose vertices at distance

k

; the corresponding entries of all lower powers vanish, while

(A^{k})_{uv} > 0

by the walk count from powers of an adjacency matrix.

 Ancestors (5)

 Incoming links (14)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (1)

Graph distance by

Wikipedia Bot  1

Graph distance refers to a measure of distance between nodes (or vertices) in a graph. In graph theory, nodes are the individual entities (like cities, web pages, etc.), and edges are the connections or relationships between these entities. There are a few different interpretations and methodologies for calculating graph distance, depending on the type of graph and the specific context: 1. **Shortest Path Distance**: The most common definition of graph distance is the shortest path distance between two nodes.

 Read the full article

  See all articles in the same topic Create my own version