## You are here

Homedistance (in a graph)

## Primary tabs

# 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* $\diam G:=\max_{{(x,y)\in V(G)^{2}}}d(x,y)$ (the maximum distance between two vertices of $G$) and the *radius* $\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).

Defines:

diameter (of a graph), radius (of a graph), central vertex

Related:

Graph, Path, Diameter3, PathConnected

Synonym:

distance

Type of Math Object:

Definition

Major Section:

Reference

Groups audience:

## Mathematics Subject Classification

05C12*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections