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?
On one quantity in a finite graph
1 Answers
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.
-
0Thank 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)$ – 2012-05-10