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