Radius of a graph: Difference between revisions

Latest revision as of 20:02, 27 May 2012

Template:Undirected graph numerical invariant

Definition

The radius of a graph is defined for any connected graph as the radius of the metric space induced by it. Explicitly, for a graph $G$ with vertex set $V(G)$ , it is:

$\min _{x\in V(G)}\left(\max _{y\in V(G)}d(x,y)\right)$

where $d$ denotes the distance between two vertices. In words, the radius of a graph is the minimum, over all vertices, of the eccentricity of that vertex.

Note that for a finite graph, the radius is finite. For an infinite graph, the radius may be finite or $\infty$ .

For a graph that is not connected, we can consider the radius to be either $\infty$ or undefined.

Related invarants

Invariant	Meaning	Relation with radius
Diameter of a graph	maximum of distances between pairs of vertices	Radius $\leq$ Diameter $\leq$ Twice the radius

@@ Line 3: / Line 3: @@
 ==Definition==
-The '''radius of a graph''' is defined for any [[connected graph]] as the radius of the [[metric space induced by a connected space|metric space induced by it]]. Explicitly, for a graph <math>G</matH> with vertex set <math>V(G)</math>, it is:
+The '''radius of a graph''' is defined for any [[connected graph]] as the radius of the [[metric space induced by a connected graph|metric space induced by it]]. Explicitly, for a graph <math>G</matH> with vertex set <math>V(G)</math>, it is:
 <math>\min_{x \in V(G)} \left(\max_{y \in V(G)} d(x,y)\right)</math>