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):=\mathrm{\infty }.$

Two basic graph invariants involving distance are the diameter $\mathrm{diam}G:={\max }_{(x,y)\in V{(G)}^2}d(x,y)$ (the maximum distance between two vertices of $G$) and the radius $\mathrm{rad}G:={\min }_{x\in V(G)}{\max }_{y\in V(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