|
|
|
Revision difference : distance (in a graph) |
| Version 6 |
Version 5 |
| The \emph{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.$ |
Given vertices $x$ and $y$, their \emph{distance} $d(x,y)$ is the minimal length of an $x-y$ path. If there is no $x-y$ path then $d(x,y) = \infty$. |
|
|
| Two basic graph invariants involving distance are the \emph{diameter} $\diam G := \max_{(x,y)\in V(G)^2} d(x,y)$ (the maximum distance between two vertices of $G$) and the \emph{radius} $\rad G := \min_{x\in V(G)} \max_{y\in V(G)} d(x,y)$ (the maximum distance of a vertex from a \emph{central} vertex of $G$, i.e. a vertex such that the maximum distance to another vertex is minimal). |
|
|
\footnotesize{Adapted with permission of the author from \emph{\PMlinkescapetext{Modern Graph Theory}} by B\'{e}la Bollob\'{a}s, published by Springer-Verlag New York, Inc., 1998.} |
|
|
|
|
