Radius of a graph: Difference between revisions

Revision as of 19:58, 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, it is:

$\min _{x\in G}\left(\max _{y\in 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 7: / Line 7: @@
 <math>\min_{x \in G} \left(\max_{y \in G} d(x,y)\right)</math>
-where <math>d</math> denotes the distance between two vertices.
+where <math>d</math> denotes the distance between two vertices. In words, the radius of a graph is the minimum, over all vertices, of the [[eccentricity of a vertex|eccentricity of that vertex]].
 Note that for a [[finite graph]], the radius is finite. For an infinite graph, the radius may be finite or <math>\infty</math>.
@@ Line 13: / Line 13: @@
 For a graph that is not connected, we can consider the radius to be either <math>\infty</math> or undefined.
-==Related notions==
+==Related invarants==
-* [[Diameter of a graph]]
+{| class="sortable" border="1"
-* [[Eccentricity of a graph]]
+! Invariant !! Meaning !! Relation with radius
+|-
+| [[Diameter of a graph]] || maximum of distances between pairs of vertices || Radius <math>\le</math> Diameter <math>\le</math> Twice the radius
+|}