# 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):=\infty.$

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