distance (in a graph)


The distance d(x,y) of two vertices x and y of a graph G is the length of the shortest path (or, equivalently, walk) from x to y. If there is no path from x to y (i.e. if they lie in different components of G), we set d(x,y):=.

Two basic graph invariants involving distance are the diameter diamG:=max(x,y)V(G)2d(x,y) (the maximum distance between two vertices of G) and the radius radG:=minxV(G)maxyV(G)d(x,y) (the maximum distance of a vertex from a central vertex of G, i.e. a vertex such that the maximum distance to another vertex is minimal).

Title distance (in a graph)
Canonical name DistanceinAGraph
Date of creation 2013-03-22 12:31:32
Last modified on 2013-03-22 12:31:32
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 11
Author CWoo (3771)
Entry type Definition
Classification msc 05C12
Synonym distance
Related topic Graph
Related topic Path
Related topic Diameter3
Related topic PathConnected
Defines diameter (of a graph)
Defines radius (of a graph)
Defines central vertex