größter existierender Abstand in einem Graphen.

Dabei wird der Abstand d_G(x, y) zweier Ecken x und y in einem zusammenhängenden Graphen G durch die Länge eines kürzesten Weges von x nach y definiert, und man setzt d_G(x, x) = 0.

Die Exzentrizität einer Ecke v ∈ E(G) wird gegeben durch

\begin{eqnarray}e(v,G)=\rm{max}\{{d}_{G}(x,v)|x\in E(G)\}.\end{eqnarray}

Die Größen diam(G) = max{e(x, G)|x ∈ E(G)} bzw. rad(G) = min{e(x, G)|x ∈ E(G)} nennt man Durchmesser bzw. Radius von G.

Folgende Abschätzungen lassen sich schnell nachweisen:

\begin{eqnarray}\text{rad(}G\text{)}\le \text{diam(}G\text{)}\le \text{2rad(}G\text{)}\text{.}\end{eqnarray}

Beide Ungleichungen sind bestmöglich, denn es gilt z. B. rad(C) = diam(C) = ⌊n/2⌋ für einen Kreis der Länge n und rad(W) = p und diam(W) = 2p für einen Weg der Länge 2p.

Ist diam(G) ≥ 4, so beweist man mit etwas mehr Aufwand \(\rm{diam}(\bar{G})\,\le \,2\), wobei \(\bar{G}\) der Komplementärgraph von G ist. Daher ist der Durchmesser eines selbstkomplementären Graphen höchstens 3. Diese Beobachtung geht auf G. Ringel (1963) zurück.

Das Zentrum eines Graphen besteht aus allen Ecken x mit e(x, G) = rad(G). Schon im Jahre 1869 hat C. Jordan gezeigt, daß das Zentrum eines Baumes aus einer Ecke oder zwei adjazenten Ecken besteht.