Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $(G,E)$ be a finite undirected graph, and $d$ be the usual shortest path distance on $G$. The graph is not necessary connected, so $d(v',v'') = \infty$ if there are no paths from $v$ to $v'$. For $A\subseteq G$ we put $$ d(v,A) = \min\limits_{u\in A}d(v,u). $$ My question is the following: let us define for $A\subseteq G$ $$ m(A) = \max\limits_{v\in A}d(v,G\setminus A). $$ Is there a name for $m(A)$, maybe you can give a reference on this?

share|cite|improve this question
up vote 1 down vote accepted

I've not found a specific term for what you're looking for, but it seems similar to Eccentricity.

The eccentricity $\epsilon(v)$ of a graph vertex $v$ in a connected graph $G$ is the maximum graph distance between $v$ and any vertex $u$ of $G\backslash \{v\}$.

If you define the graph distance between a set and a vertex as you did above: $d(v,A) = \min\limits_{u\in A}d(v,u)$, then you could generalise this definition to vertex sets:

The eccentricity $\epsilon(A)$ of a set of graph vertices $A$ in a connected graph $G$ is the maximum graph distance between $A$ and any vertex $u$ of $G\backslash A$.

i.e. $\epsilon(A) = \max\limits_{u \in G \backslash A} d(u,A)$

So strictly speaking, $\epsilon(G \backslash A) = \max\limits_{u \in A} d(u,G \backslash A)$, which looks like what you asked for.

Not quite an answer, but hopefully it'll help in some way.

share|cite|improve this answer
Thank you for the answer, an interesting observation. I thought about the connections between $m(A)$ and the eccentricity, but mostly focused on the radius of $A$ which in the end doesn't seem to be connected anyhow to $m(A)$ – Ilya May 10 '12 at 12:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.