PlanetMath: distance (in a graph)

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (198)
Orphanage
Unclass'd
Unproven (498)
Corrections (25)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

distance (in a graph)

(Definition)

The distance of two vertices and of a graph is the length of the shortest path (or, equivalently, walk) from to . If there is no path from to (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 ${\mathrm{diam}}G := \max_{(x,y)\in V(G)^2} d(x,y)$ (the maximum distance between two vertices of ) 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 , i.e. a vertex such that the maximum distance to another vertex is minimal).

Anyone with an account can edit this entry. Please help improve it!

"distance (in a graph)" is owned by Cosmin. [ full author list (2) | owner history (1) ]

(view preamble)